Trenul Iaşi-Bucureşti trece prin N staţii, numerotate în ordinea de pe traseu de la 1 (Iaşi) la N (Bucureşti).
În staţiile prin care trece trenul pot fi ataşate vagoane (unul sau mai multe, pe rând, numai la începutul sau la sfârşitul trenului) sau pot fi desprinse vagoane (tot unul sau mai multe, pe rând, şi tot numai de la începutul sau de la sfârşitul trenului).
Angajaţii CFR au o listă în care pentru fiecare vagon este reţinută staţia la care vagonul este ataşat la tren şi respectiv staţia la care vagonul trebuie să fie desprins de tren.
Cerinţă
Determinaţi o planificare a operaţiilor de ataşare vagoane/desprindere vagoane astfel încât să fie respectată lista angajaţilor CFR (dacă este posibil).
Date de intrare
Fişierul de intrare cfr.in conţine pe prima linie numărul natural N, reprezentând numărul de staţii, urmat de numărul natural M, reprezentând numărul de vagoane. Urmează M linii, descriind lista angajaţilor CFR. Pe linia i+1 sunt scrise două numere naturale x y (1≤x<y≤N) cu semnificaţia că vagonul i va fi ataşat la tren în staţia x şi va fi desprins de tren în staţia y. Numerele scrise pe aceeaşi linie sunt separate prin spaţii.
Date de ieşire
Fişierul de ieşire cfr.out va conţine operaţiile care trebuie să fie executate (în ordinea executării lor), câte o operaţie pe o linie. O operaţie are următorul format: 1 x cu semnificaţia "vagonul x este ataşat la începutul trenului" 2 x cu semnificaţia "vagonul x este ataşat la sfârşitul trenului" 3 x cu semnificaţia "vagonul x este desprin de tren"
Dacă problema nu are soluţie fişierul de ieşire va conţine o singură linie pe care va fi scrisă valoarea 0.
Restricţii
1 ≤ N ≤ 200
1 ≤ M ≤ 200
Este posibil ca un tren să meargă fără vagoane.
În planificare un vagon trebuie să fie ataşat o singură dată şi desprins o singură dată.
Exemple
cfr.in
cfr.out
Explicaţie
10 5
2 9
4 9
1 10
3 8
5 8
1 3
1 1
1 4
2 2
1 5
3 5
3 4
3 2
3 1
3 3
În staţia 1 este ataşat la începutul trenului vagonul 3. Trenul: 3
În staţia 2 este ataşat la începutul trenului vagonul 1. Trenul: 1 3
În staţia 3 este ataşat la începutul trenului vagonul 4. Trenul 4 1 3
În staţia 4 este ataşat la sfârşitul trenului vagonul 2. Trenul: 4 1 3 2
În staţia 5 este ataşat la începutul trenului vagonul 5. Trenul: 5 4 1 3 2
În staţia 8 este desprins vagonul 5. Trenul: 4 1 3 2