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

Niveau 3

É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$

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
2
0 0 1 1
1 1 0 0
Exemple de sortie
JAMAIS
Exemple d'entrée
3
1 5 3 6
0 0 2 2
2 2 1 5
Exemple de sortie
3 6