Les duenyes del graf P17061

La Natàlia, la Júlia, la Matilda i la Clara son un grup d’amigues de la FME més conegudes com “les duenyes”. Últimament estan obsessionades amb els problemes d’Algorísmia, més concretament amb els problemes de grafs, fins al punt que se les coneix com “les duenyes del graf”. Per altra banda, a en Calatayud li fan pànic els grafs, i en vol escapar com sigui.

Les duenyes han creat un graf no dirigit i connex, han colocat en Calatayud al vèrtex s, i una sortida al vèrtex t. Podrà en Calatayud arribar a la sortida fent passos de distància dos? Aquí, diem que un pas de distància dos des d’un vèrtex x fins a un vèrtex z és vàlid si existeix algun vèrtex y adjacent tant a x com a z.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arestes m, seguits d’m parells x y indicant una aresta entre x i y, amb x ≠ y, seguits d’s i t. Suposeu 2 ≤ n ≤ 10⁵, n − 1 ≤ m ≤ 5n, que els vèrtexs es numeren entre 0 i n−1, que no hi ha arestes repetides, que el graf és connex, i s ≠ t.

Sortida

Per a cada cas, escriviu “SI” si en Calatayud podrà escapar del graf, o “NO” altrament.