Rivière agitée – Épreuve régionale 2017

Énoncé¶

Joseph Marchand part faire une sieste sur sa barque au milieu de la rivière. La rivière est à son plus paisible, c'est l'occasion idéale !

Soudainement une tempête se lève, Joseph ne parvient plus à manœuvrer. Sa barque est emportée par le courant. Il se laisse emporter jusqu'à trouver un endroit plus calme où il pourra rejoindre la côte. Heureusement, il a pensé à son talkie-walkie. Vous qui êtes resté sur la côte, aidez-le en lui donnant le prochain emplacement où il pourra enfin manœuvrer, si celui-ci existe, ou « JAMAIS » le cas échéant.

Il y a plusieurs courants dans la rivière, chacun envoyant depuis un emplacement $(a, b)$ vers un autre emplacement $(c, d)$. Il ne peut pas y avoir deux courants partants du même emplacement.

La barque de Joseph se trouve initialement à l'emplacement $(0, 0)$. Joseph pourra rejoindre la côte s'il atteint un emplacement dont ne part aucun courant.

Entrée¶

L'entrée comprendra plusieurs lignes :

• La première ligne contiendra un entier $N$, le nombre de courants de la rivière.
• $N$ lignes suivront, chacune sera de la forme $a, b, c, d$, ce qui signifie qu'il existe un courant de la position $(a, b)$ vers $(c, d)$.

Sortie¶

Si Joseph se trouve indéfiniment emporté par le courant vous afficherez « JAMAIS », sinon affichez deux entiers $x$ et $y$ séparés par une espace, où $(x, y)$ est la première position à partir de laquelle Joseph peut manœuvrer.

Contraintes¶

• $1 \le N \le 1\ 000$
• $0 \le a, b, c, d \le 100$