Пигги (бос уақытында Жұлдызаралық байланыс хаттамасы комиссиясын басқарады) күрделі аппараттық мәселеге тап болды. Ағаш құрылымын құрайтын $(n - 1)$ талшықты-оптикалық желімен байланысқан $n$ ретрансляциялық станциядан тұратын ең жаңа коммуникациялық тор ақыры іске қосуға дайын. Алайда жүйеге қуат беру аса сақтықпен жүргізілуі тиіс.
Белсендіру процесі белгілі бір жолдар бойымен лазерлік импульстарды жіберуді қамтиды. Жол ретінде екі станция арасындағы жалғыз қарапайым маршрут анықталады. Комиссия заңгерлерін түні бойы ұйықтатпайтын құбылыс — «Кванттық кері ағын интерференциясының» апатты қаупіне байланысты келесі хаттама қатаң сақталуы керек:
- Тарату жолдары бірінен соң бірі орнатылуы тиіс.
- Қуаттың күрт артуын болдырмау үшін, әрбір жаңадан орнатылған жол бұрынғы кез келген жол арқылы белсендірілген станциялар жиынымен ең көбі бір станцияны ғана ортақ пайдалана алады.
Формалды түрде, $S$ — қазіргі уақытта белсендірілген станциялар жиыны болсын. $V(P)$ станциялар жиынынан тұратын кез келген жаңа $P$ жолы үшін $|V(P) \cap S| \le 1$ шарты орындалуы тиіс. Жол бойымен импульс сәтті жіберілгеннен кейін, сол жолдың бойындағы барлық станциялар белсендірілген $S$ жиынының бөлігі болып саналады.
Сіздің миссияңыз (егер оны қабылдауды таңдасаңыз) — бүкіл желідегі әрбір станцияны белсендіру үшін қажетті лазерлік импульстардың ең аз санын анықтау және заң бөлімінің талабын қанағаттандыру үшін осындай жолдар тізбегінің бірін ұсыну.

Алғашқы екі мысал тест жағдайының иллюстрациясы. 2-жағдайда екінші импульс біріншісімен тек $2$-станцияны ғана ортақ пайдаланып, интерференция болмау ережесін қанағаттандыратынына назар аударыңыз.
Кіріс деректер
Бірнеше тест жиынтығы берілген. Кірістің бірінші жолында тест жиынтықтарының санын білдіретін бүтін $T$ ($1 \le T \le 10^4$) саны берілген. Әрбір тест жиынтығы үшін:
Бірінші жолда тордағы станциялар санын білдіретін бүтін $n$ ($2 \le n \le 3 \times 10^5$) саны берілген.
Келесі $(n - 1)$ жолдың $i$-ші жолында $u_i$ мен $v_i$ станциялары арасындағы екі бағытты талшықты-оптикалық желіні сипаттайтын екі бүтін $u_i$ және $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) сандары берілген.
Желілердің ағаш құрайтынына және барлық тест жиынтықтары бойынша $n$ мәндерінің қосындысы $3 \times 10^5$ шамасынан аспайтынына кепілдік беріледі.
Шығыс деректер
Әрбір тест жиынтығы үшін бірінші жолда жолдардың ең аз $k$ санын шығарыңыз. Одан кейін $k$ жол шығарыңыз, олардың әрқайсысында тізбектегі $i$-ші жолдың шеткі нүктелерін білдіретін екі бүтін $a_i$ және $b_i$ сандары болуы керек. Егер жол бір ғана станциядан тұрса, $a_i$ мен $b_i$ тең болуы мүмкін екенін ескеріңіз.
Егер бірнеше оңтайлы тізбек бар болса, интерференция болмау хаттамасын қатаң сақтайтын кез келгені қабылданады.
Мысал
Кіріс деректер
3 3 1 2 2 3 5 1 2 2 3 2 4 2 5 7 1 2 1 3 2 4 2 5 3 6 3 7
Шығыс деректер
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5