Ion s-a mutat intr-un sat din Alaska. Pentru a ajunge din satul sau in cel mai apropiat oras, el trebuie sa traverseze un rau mare si involburat, care nu ingheata niciodata. Ion inhama cainii la sanie si apoi leaga de sanie o barca. Cand ajunge la rau, Ion se urca in barca si transporta pe rand cainii pe celalalt mal. La ultimul transport, Ion leaga sania de barca si astfel la sfarsit ajunge pe celalalt mal cu caini, barca si sanie. Pare destul de simplu, dar nu este intotdeauna asa. Unii caini se dusmanesc reciproc si nu pot fi lasati singuri (fara Ion) pe acelasi mal. Cainii care nu se dusmanesc pot fi lasati singuri pe acelasi mal fara nici o problema. Evident, Ion stie care caini se dusmanesc reciproc.

De exemplu, anul acesta Ion are 5 caini: Labus, Grivei, Rex, Zdreanta si Costel. Grivei se dusmaneste cu Labus, Zdreanta si Costel. Rex se dusmaneste cu Labus si Zdreanta. Ceilalti caini nu au aversiuni unii fata de ceilalti. Prin urmare, Ion are nevoie de o barca cu 3 locuri, astfel incat atunci cand traverseaza raul sa poata transporta doi caini si trebuie sa faca minim 7 traversari, dupa cum urmeaza:
1. transporta pe Grivei si Rex de pe malul 1 pe malul 2;
2. il aduce inapoi pe Grivei pe malul 1;
3. transporta pe Costel si Grivei pe malul 2;
4. transporta pe Grivei si Rex inapoi pe malul 1;
5. transporta pe Zdreanta si pe Labus pe malul 2;
6. revine pe malul 1 fara a aduce nici un caine inapoi
7. leaga sania de barca, transporta pe Grivei si pe Rex pe maul 2 si isi continua calatoria.

Observati ca la nici un moment doi caini care se dusmanesc nu au fost lasati singuri pe acelasi mal. Daca Costel si Labus s-ar fi dusmanit, o barca cu 3 locuri nu ar mai fi fost suficienta.

Cerinta

Scrieti un program care sa determine X, numarul minim de locuri din barca pentru a transporta toti cainii, precum si o modalitate de a transporta cainii efectuand un numar minim de transporturi cu o barca cu X locuri, astfel incat la nici un moment doi caini care se dusmanesc sa fie lasati singuri pe acelasi mal.

Date de intrare

Fisierul de intrare caini.in contine pe prima linie un numar natural N reprezentand numarul de caini pe care ii are Ion. Cainii sunt numerotati de la 1 la N. Pe cea de a doua linie se afla un numar natural K reprezentand numarul de perechi de caini care se dusmanesc reciproc. Fiecare dintre urmatoarele K linii contine doua numere naturale separate printr-un spatiu a b cu semnificatia "cainii a si b se dusmanesc reciproc".

Date de iesire

Fisierul de iesire caini.out contine pe prima linie doua numere naturale separate printr-un spatiu X Y; X reprezinta numarul minim de locuri din barca, astfel incat cainii sa poata fi transportati; Y reprezinta numarul minim de transporturi pe care Ion trebuie sa le faca pentru a transporta toti cainii folosind o barca cu X locuri.

Restrictii si precizari

1<=N<=10
In fisierul de intrare, o pereche de caini care se dusmanesc este specificata o singura data.

Exemplu

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi