== include(page="template/taskheader" task_id="bribe") ==

Poveste şi cerinţă...

Doi oameni pe care, pentru a le păstra anonimitatea, îi vom numi Costel si Costin, participă la lotul de informatică. Costel face parte din comisie, în timp ce Costin este concurent.

h2. Date de intrare

Cei doi au făcut o înţelegere cel putţin bizară: contra unor foloase materiale, Costel îl va ajuta pe Costin să obţină 100 de puncte la una dintre probleme. Stiind că toate problemele de la lot au ca output un singur număr, Costin a ales deja 50 de numere preferate R ~i~ , (1 ≤ i ≤ 50) pe care i le-a transmis lui Costel. Acesta trebuie acum ca, pentru o problemă, să genereze 50 de teste pentru care răspunsurile sunt cele 50 de numere alese de Costin.

Fişierul de intrare $bribe.in$ ...

Problema aleasă de Costel pentru a pune în aplicare planul este următoarea: “Se dă un arbore (graf conex neorientat aciclic) format din _N_ noduri, 1 ≤ _N_ ≤ 400. Pentru acesta, se cere să se determine **câte mulţimi maxime de noduri independente există pentru arborele dat** . O mulţime maximă de noduri independente se defineste ca fiind o mulţime de noduri cu cardinal maxim, astfel încât nu există două noduri în mulţime care să fie unite de o muchie din arborele original.”

h2. Date de ieşire

Din cauza unui accident nefericit care îl împiedică să mai continue, Costel v-a însărcinat pe voi să continuati planul. Construiti 50 de arbori pentru care, pentru fiecare arbore _i_, răspunsul la problema aleasă este numărul R ~i~.

În fişierul de ieşire $bribe.out$ ...

h2. Restricţii si precizari

h2. Restricţii

Fiecare fisier de intrare are următorul format:

* $... ≤ ... ≤ ...$

     • linia i (1 ≤ i ≤ 50): R ~i~,un număr întreg pozitiv , (1 ≤ R ~i~ ≤ 10^18^) , reprezentând răspunsul dorit pentru testul cu numărul _i_.
 
In fisierul de iesire corespunzator trebuie sa afisati forma a 50 de arbori , astfel încât pentru arborele cu numarul _i_ răspunsul la problema propusă de Costel este R ~i~ . Arborii vor fi afisati secvential în fisierul de ieşire. Un arbore individual va fi afişat în următorul mod:
 
     • linia 1: un număr întreg N ,  1 ≤ N ≤ 400 , reprezentând dimensiunea arborelui.
 
     • linia 2+i (0 ≤ _i_ ≤ N-2): a,b doua numere intregi 0 ≤ _a,b_ ≤ _N_ -1 (a ≠ b) , semnificând existenta unei muchii între nodurile _a_ si _b_.
 
Se garantează că există solutie pentru toate testele.
 
h2. Punctare
 
Pentru un test punctajul maxim se obtine dacă pentru fiecare din cei 50 de arbori, răspunsul la problema propusă de Costel corespunzător arborelui _i_ este R ~i~ . În plus, fiecare arbore afisat în fisierul de intrare trebuie să contină cel mult 400 de noduri.
 
| Subtask | Punctaj | Constrangeri |
|1        |13 puncte| 1 ≤ R ~i~ ≤ 20|
|2        |6 puncte | 1 ≤ R ~i~ ≤ 100|
|3        |5 puncte | 1 ≤ R ~i~ ≤ 200|
|4        |7 puncte | 1 ≤ R ~i~ ≤ 10^18^ , R ~i~ este putere a lui 2 |
|5        |50 puncte| 1 ≤ R ~i~ ≤ 2*10^9^|
|6        |19 puncte| 1 ≤ R ~i~ ≤ 10^18^ |

h2. Exemplu
table(example). |_. bribe.in |_. bribe.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
  2
| 7
0 1
0 2
2 3
1 4
4 5
4 6
8
0 1
0 2
0 3
3 4
5 4
5 6
5 7

|
h3. Explicaţie

...

Pentru primul exemplu, trebuie generat un arbore care are exact 3 multimi de noduri independente. Pentru arborele generat, cele 3 multimi posibile care  pot  fi alese sunt cele din imaginile  urmatoare(nodurile unei multimi fiind cele cu marginea ingrosata):
!problema/bribe?graph1.png!
!problema/bribe?graph2.png!
!problema/bribe?graph3.png!
 

== include(page="template/taskfooter" task_id="bribe") ==