Pe o masa se afla N
pahare de plastic, numerotate distinct de la 1
la N. Paharele pot
fi puse unul in altul, astfel formandu-se turnuri de pahare.
Se da o secventa de mutari de forma a
b, cu semnificatia "turnul care contine paharul a
va fi pus peste turnul care contine paharul cu numarul b".
Daca paharele a si
b sunt in acelasi
turn sau daca a=b
atunci mutarea nu are nici un efect.
Mutarile trebuie sa fie executate in ordinea
in care ele apar in secventa.
De exemplu, sa consideram ca avem 7 pahare, iar sirul de mutari este 1 3,
2 6, 3 6,
4 7 si 4 2.
Configuratia paharelor de pe masa se schimba astfel:
Initial: (1) (2) (3) (4) (5) (6) (7) (fiecare pahar formeaza un turn separat).
Dupa mutarea 1 3: (1 3) (2) (4) (5) (6) (7)
Dupa mutarea 2 6: (1 3) (2 6) (4) (5) (7)
Dupa mutarea 3 6: (1 3 2 6) (4) (5) (7)
Dupa mutarea 4 7: (1 3 2 6) (4 7) (5)
Dupa mutarea 4 2: (1 3 2 6 4 7)
(5)
Cerinta
Scrieti un program care sa determine mutarea 0,
adica mutarea care ar trebui sa fie executata inaintea primei mutari din secventa,
astfel incat numarul de pahare din cel mai inalt turn sa fie maxim.
Date de intrare
Fisierul de intrare turn1.in
contine pe prima linie doua numere naturale N
(numarul de pahare) si M
(numarul de mutari), separate prin spatiu. Fiecare dintre urmatoarele M
linii contine o mutare, data prin doua numere naturale a
b, separate printr-un spatiu.
Date de iesire
Fisierul de iesire turn1.out
va contine o singura linie pe care se afla mutarea 0,
specificata ca o pereche de numere naturale a
b, separate printr-un singur spatiu.
Restrictii
2 <= N <= 10000
0 <= M <= 100000
Solutia nu este in mod necesar unica.
Exemple
turn1.in
turn1.out
turn1.in
turn1.out
turn1.in
turn1.out
5 3
1 2
5 3
4 1
4 5
6 4
5 2
3 3
1 3
6 2
3 5
10 9
3 7
5 9
10 10
9 5
8 7
3 7
6 1
4 2
2 6
7 2
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi