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!

Pirmajā rindā dots viens skaitlis n, kopējais komandu skaits (2 ≤ n ≤ 10⁵). Nākamajās n/2 rindās aprakstītas 1. dienas spēles: i-tajā rindā doti divi skaitļi a_i un b_i, kas nozīmē, ka komanda a_i nospēlēja kopā ar komandu b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i). 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ā).

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 c₁, c₂, ..., c_m. Katram komandu pārim c_i, c_j savā starpā nav jābūt nospēlētai nevienai spēlei pirmo divu dienu laikā.

Virknei (c₁, c₂, ..., c_m) jābūt leksikogrāfiski vismazākai. Tas nozīmē, ka jebkurai citai m komandu virknei (d₁, d₂, ..., d_m), kas savā starpā arī nav spēlējušas nevienu spēli, pirmajā pozīcijā i, kur c_i ≠ d_i, izpildās c_i < d_i, nevis c_i > d_i. Piemēram, virkne (1, 3, 6) ir leksikogrāfiski mazāka par virkni (1, 4, 5).