La cursa prohibida de Lisboa P66335

En Bernat, en Manuel, l’Esomer i en Jan van competir al SWERC a Lisboa, on el patinet elèctric és molt convenient. En acabar la sessió de proves van decidir agafar-ne uns quants ‍i, confiant en la seu sentit d’orientació (?), intentar tornar a l’hostal. UPC-1 i UPC-3 potser no guanyarien el SWERC, però tenien clar que la cursa en patinet era seva.

Segons sembla:

• Van ignorar absolutament tots els senyals de STOP.
• L’Esomer es va quedar atrapat mentre la resta el van deixar enrere ignorant un semàfor en vermell.
• En Manuel va intentar optimitzar retallant per un troç de gespa i... es va menjar un arbre (xoc frontal, 0 punts).
• En Bernat i en Jan, finalment, es van perdre pels carrers de Lisboa. Després d’una bona estona voltant, van afirmar que havien acabat tornant al punt inicial, davant del lloc on es feien els entrenaments.

Ara bé, ells asseguren amb total convicció dues coses:

1. No van passar en cap moment per l’hostal.
2. No van travessar cap carrer en els dos sentits.

Modelem Lisboa com un graf no dirigit i connex amb n vèrtexs (els encreuaments) i m arestes (els carrers). El lloc d’entrenament se situa al vèrtex s i l’hostal al vèrtex t.

Determineu si la història del Bernat i en Jan pot ser certa: és a dir, si existeix algun camí (no ‍buit) que comença a s, evita t en tot moment, no recorre cap aresta més d’una vegada (ja ‍sigui en el mateix sentit o en sentit contrari), i ‍que acaba tornant a s.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i 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 la història del Bernat i en Jan és possible, o “NO” si en Bernat i en Jan ja no saben ni de què parlen.