== include(page="template/taskheader" task_id="trigame") ==
Poveste si cerinta...
Fat-Frumos trebuie sa o salveze pe Ileana Cosanzeana din palatul Zmeului cel Rau. Totusi, Ileana nu vrea sa fie salvata, asa ca se decid sa joace un joc. Daca va castiga, Ileana ramane la Zmeu, altfel va pleca cu Fat-Frumos.
Palatul Zmeului are $N$ camere, unele perechi de camere fiind unite prin coridoare, astfel incat din orice camera se poate ajunge in orice alta camera intr-un mod unic. Initial, luminile sunt aprinse in toate camerele. Cei doi incep jocul in camere diferite, si vor muta alternativ -- acest lucru este posibil, intrucat atat Ileana cat si Fat-Frumos au telefoane mobile. Intr-o mutare, fiecare personaj stinge lumina in camera curenta in care se afla, alege o camera vecina libera in care lumina este aprinsa si se deplaseaza in aceasta. Atat Ileana Cosanzeana cat si Fat-Frumos joaca optim: daca unul dintre ei are o strategie astfel incat sa fie sigur de victorie indiferent de mutarile adversarului, o va urma. Ileana va face prima mutare. Va pierde cel care nu va mai putea efectua nici o mutare, adica lumina este stinsa in toate camerele adiacente camerei in care se afla. Cu alte cuvinte, castigatorul este cel care muta ultimul.
Pentru ca autorul povestii nu mai stie care sunt camerele in care incep celor doua personaje, va trebui sa determinati, luand in considerare toate pozitiile initiale posibile, cate jocuri va castiga Ileana Cosanzeana.
h2. Date de intrare
Fisierul de intrare $trigame.in$ ...
Fisierul de intrare $trigame.in$ contine pe prima linie valoarea lui $N$. Urmatoarele $N$-1 linii vor contine cate doua numere naturale diferite $a b$, cu valori intre $1$ si $N$, cu semnificatia ca exista un coridor intre camerele $a$ si $b$.
h2. Date de iesire
In fisierul de iesire $trigame.out$ ...
In fisierul de iesire $trigame.out$ se va scrie un singur numar, reprezentand numarul de jocuri pe care le va castiga Ileana Cosanzeana.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 2048$
* Pentru 40% din datele de test, $2 ≤ N ≤ 64$
* Pentru alte 20% din datele de test, $2 ≤ N ≤ 256$
h2. Exemplu
table(example). |_. trigame.in |_. trigame.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
1 2
2 3
2 4
1 5
| 12
|
h3. Explicatie
...
Din cele 20 de jocuri posibile, Ileana va castiga 12 jocuri, cele in care pozitiile initiale sunt: (1, 3) (1, 4) (1, 5) (2, 3) (2, 4) (2, 5) (3, 1) (3, 4) (3, 5) (4, 1) (4, 3) (4, 5) -- primul numar din pereche este pozitia Ileanei, al doilea este pozitia lui Fat-Frumos. De exemplu, pentru (3, 5), Ileana se va deplasa in camera 2, Fat-Frumos in camera 1, ultima mutare fiind a Ileanei care va muta in camera 4, castigand jocul.
== include(page="template/taskfooter" task_id="trigame") ==
