Fişierul intrare/ieşire:	bribe.in, bribe.out	Sursă	Lot Seniori Dorohoi 2019 - Baraj 1
Autor	Adrian Budau, Vlad Gavrila	Adăugată de	brebenel mihnea stefan •tryharderul
Timp execuţie pe test	0.5 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bribe

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.

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.

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.”

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.

Restricţii si precizari

Fiecare fisier de intrare are următorul format:

  • linia i (1 ≤ i ≤ 50): R _i,un număr întreg pozitiv , (1 ≤ R _i ≤ 10¹⁸) , 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.

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.

Exemplu

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): 

Cum se trimit solutii?