N copii, numerotați de la 1 la N, se aşează în cerc, unul lângă altul, în ordinea crescătoare a numerelor lor, copilul cu numărul N ajungând să fie situat lângă copilul cu numărul 1.
Un copil din cerc are o minge. El o aruncă unui alt copil din cerc. Acesta o aruncă și el unui alt copil din cerc care nu a atins vreodată mingea, … șamd. Fiecare aruncare este notată printr-o pereche de numere naturale distincte (X,Y) cu semnificația că copilul cu numărul X aruncă mingea copilului cu numărul Y care nu a mai atins mingea până în acel moment.

Cerințe

Cunoscându-se numerele N, K și cele K perechi de numere corespunzătoare celor K aruncări să se determine:
1) Numărul copiilor care nu ating niciodată mingea.
2) Traseul parcurs de minge plecând de la copilul care are mingea la începutul jocului, până la copilul care nu mai aruncă mingea.

Date de intrare

Fișierul de intrare minge.in conține
– pe prima linie, un număr natural p; pentru toate testele de intrare, p poate avea doar valoarea 1 sau valoarea 2;
– pe a doua linie, cele două numere naturale N K, separate printr-un spațiu.
– pe fiecare dintre următoarele K linii (câte una pentru fiecare aruncare), câte o pereche de numere naturale X Y, separate printr-un spațiu, cu semnificația: copilul cu numărul X aruncă mingea copilului cu numărul Y.

Date de ieșire

– Dacă valoarea lui p este 1, atunci se va rezolva numai cerința 1. În acest caz, fişierul minge.out va conţine pe prima linie un număr natural reprezentând numărul copiilor care nu ating niciodată mingea
– Dacă valoarea lui p este 2, atunci se va rezolva numai cerința 2. În acest caz, fişierul minge.out va conţine pe prima linie, traseul parcurs de minge plecând de la copilul care are mingea la începutul jocului, până la copilul care nu mai aruncă mingea; traseul este descris prin șirul numerelor copiilor care ating mingea, separate prin câte un spațiu, în ordinea în care este aruncată mingea.

Restricții și precizări

• 6 ≤ N ≤ 10000
• 1 ≤ X,Y ≤ N
• 1 ≤ K ≤ N-1
• traseul parcurs de minge este unic pentru fiecare set de date de intrare
• pentru rezolvarea corectă a primei cerințe se acordă 50% din punctaj iar pentru rezolvarea corectă a celei de-a doua cerințe se acorda 50% din punctaj

Exemplul 1:

minge.in

1
7 4
4 3
2 6
3 1
6 4

minge.out

2

Explicație

p=1. Se rezolvă doar cerința 1. Sunt N=7 copii. Se fac K=4 aruncări. Sunt 2 copii care nu ating mingea, cei cu numerele 5 și 7.

Exemplul 1:

minge.in

2
7 4
4 3
2 6
3 1
6 4

minge.out

2 6 4 3 1

Explicație

p=2. Se rezolvă doar cerința 2. Sunt N=7 copii. Se fac K=4 aruncări.
Traseul parcurs de minge pornește de la copilul cu numărul 2 și se termină la copilul cu numărul 1 este: 2 6 4 3 1, deoarece se fac aruncările: (2,6),(6,4),(4,3),(3,1)