Salts de dos en dos S97190

Donats un graf no dirigit i dos vèrtexs $s$ i $t$, calculeu el mínim nombre de salts que cal fer per anar des d’$s$ fins a $t$. Aquí, direm que un salt entre dos vèrtexs $x$ i $z$ és possible si existeix algun vèrtex $y$ adjacent tant a $x$ com a $z$.

Entrada

L’entrada consisteix en diversos grafs. Cada cas comença amb $n$, $m$, $s$ i $t$, seguit d’$m$ parells $x$ $y$, amb $x \ne y$, que indiquen una aresta entre $x$ i $y$. Suposeu $2 \le n \le 10^5$, $0 \le m \le 5n$, $s \ne t$, que els vèrtexs es numeren entre 0 i $n - 1$, i que no hi ha arestes repetides.

Sortida

Per a cada graf, escriviu el mínim nombre de salts per anar des d’$s$ fins a $t$. Si és impossible, escriviu “NO”.

Observació

Encara que s’obtingui un verd, només es donarà la màxima puntuació a aquelles solucions de cost $\Theta(n+m)$.