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 ≠ y, que indiquen una aresta entre x i y. Suposeu 2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 5n, s ≠ 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 Θ(n+m).