Engranatges P57302

Donat un sistema d’engranatges, heu de determinar si podrà girar adequadament, o si algun dels engranatges provocarà un bloqueig del sistema en intentar girar en les dues direccions. Concretament, dos engranatges adjacents han de girar en sentits oposats.

Per exemple, tres engranatges en fila poden girar sense problemes, mentre que, en disposició de triangle, un dels tres genera un conflicte, ja que hauria de girar en els dos sentits per ser consistent amb cadascun dels engranatges adjacents:

0.5

0.4

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre $n$ d’engranatges i el nombre $m$ de parelles d’engranatges adjacents. Després vénen $m$ parells diferents $x$ $y$, amb $x \ne y$, indicant que l’engranatge $x$ i l’engranatge $y$ són adjacents. Suposeu $1 \le n \le 10^4$, $0 \le m \le 5n$, i que els engranatges es numeren entre 0 i $n - 1$.

Sortida

Per a cada cas, escriviu “SI” si el sistema podrà girar sense tenir cap conflicte de direccions, i “NO” en cas contrari.