Copiii din cartier s-au adunat pe terenul de fotbal al scolii si se antreneaza pentru campionatul de fotbal pe oras. Fiecare copil primeste de la antrenor un tricou. Tricourile sunt numerotate distinct de la 1 la N, si sunt impartite astfel incat cel mai bun jucator primeste tricoul 1, iar cel mai slab tricoul N.
Copii vor fi impartiti in doua echipe avand acelasi numar de jucatori in modul urmator. Fiecare jucator face o lista formata din copiii cu care el nu ar vrea sa joace in aceeasi echipa. Evident, fiecare ar vrea sa aiba in echipa jucatori mai buni decat el si, prin urmare, in lista unui copil nu apar decat jucatori mai slabi decat el.

Cerinta

Scrieti un program care sa determine imparta copiii in doua echipe avand acelasi numar de jucatori, astfel incat preferintele fiecarui copil sa fie respectate.

Date de intrare

Fisierul de intrare echipe1.in contine pe prima linie un numar natural par N (numarul de copii). Fiecare dintre urmatoarele N linii contine o lista de preferinte. Mai exact cea de a (i+1)-a linie din fisier este lista jucatorilor cu care copilul i nu doreste sa fie in echipa, sub forma: K A₁ A₂ ... A_K unde K este numarul de jucatori cu care copilul i nu vrea sa fie in aceeasi echipa, iar A₁, A₂, ..., A_K sunt jucatorii respectivi.

Date de iesire

Fisierul de iesire echipe1.out contine pe prima linie numerele de ordine ale jucatorilor din una dintre echipe, separate prin spatii. Ordinea in care sunt specificati jucatorii nu conteaza.

Restrictii

• N <=1000, N par
• Exista intotdeauna solutie pentru datele de test, nu neaparat unica.

Exemple

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