Nosaukums
Nespēlētāji (nespele)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
44%

Definīcija

Gudrinieku ciemā tiek rīkots hokeja turnīrs, kurā piedalās n komandas (n – pāra skaitlis), sanumurētas ar numuriem no 1 līdz n. Sacensības notika 2 dienas. Katrā no dienām visas komandas sadalījās pa pāriem un katrs pāris savā starpā izspēlēja vienu spēli.

Tomēr pēc šīm divām dienām kļuva skaidrs, ka uzvarētāju no šiem rezultātiem noteikt ir pagrūti. Tāpēc turnīra žūrija pieņēmusi lēmumu 3. dienā izvēlēties lielāko komandu daudzumu, kas savā starpā nav nospēlējušas nevienu spēli, un sarīkot spēles starp katru komandu pāri no izvēlētajām.

Piemēram, ja ir 6 komandas, pirmajā dienā nospēlēja pāri (1, 2), (3, 5), (4, 6), un otrajā dienā nospēlēja pāri (1, 2), (3, 4), (5, 6), tad 3. dienā žūrija varēja izvēlēties 3 komandas ar numuriem 1, 3, 6, kas ir lielākais iespējamais skaits. Tikpat labi žūrija varēja izvēlēties arī, piemēram, trijnieku 1, 4, 5.

Jums tika uzticēts atrast lielāko tādu komandu kopu! Tā kā dažādu atrisinājumu var būt daudz, izvadiet leksikogrāfiski mazāko sarakstu ar komandām!


Ievaddatu raksturojums

Pirmajā rindā dots viens skaitlis n, kopējais komandu skaits (2 ≤ n ≤ 105). Nākamajās n/2 rindās aprakstītas 1. dienas spēles: i-tajā rindā doti divi skaitļi ai un bi, kas nozīmē, ka komanda ai nospēlēja kopā ar komandu b(1 ≤ ai, bi ≤ n, a bi). Nākamajās n/2 rindās analoģiski aprakstītas 2. dienas spēles.

Garantēts, ka katras dienas spēles ir korekts komandu sadalījums pāros. Ievērojiet, ka divas komandas var spēlēt kopā arī divas spēles (pirmajā un otrajā dienā).


Izvaddatu raksturojums

Pirmajā rindā izvadiet vienu skaitli m – lielāko komandu skaitu, kas savā starpā neizspēlēja nevienu spēli. Nākamajā rindā izvadiet virkni no m komandu numuriem c1, c2, ..., cm. Katram komandu pārim cicsavā starpā nav jābūt nospēlētai nevienai spēlei pirmo divu dienu laikā.

Virknei (c1c2, ..., cm) jābūt leksikogrāfiski vismazākai. Tas nozīmē, ka jebkurai citai m komandu virknei (d1, d2, ..., dm), kas savā starpā arī nav spēlējušas nevienu spēli, pirmajā pozīcijā i, kur ci ≠ di, izpildās ci < di, nevis ci > di. Piemēram, virkne (1, 3, 6) ir leksikogrāfiski mazāka par virkni (1, 4, 5).


Paraugdati

Stdin
6
1 2
6 4
3 5
2 1
4 3
5 6
Stdout
3
1 3 6 

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.