Annettuna on puu (eli syklitön yhtenäinen verkko), jossa on n solmua. Kahden solmun etäisyys on lyhimmän polun pituus (kaarten määrä) solmujen välillä.

Tehtäväsi on etsiä solmujen järjestys, jossa jokaisen kahden peräkkäisen solmun etäisyys on enintään 3.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Tämän jälkeen jokaisen testin ensimmäisellä rivillä on kokonaisluku n: solmujen määrä. Tämän jälkeen on n-1 riviä, jotka kuvaavat puun kaaret.

Tuloste

Tulosta jokaisesta testistä n lukua: solmujen järjestys. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Esimerkki

Syöte:

2
4
1 2
1 3
1 4
3
1 2
2 3

Tuloste:

1 2 3 4
2 1 3

Osatehtävä 1 (29 pistettä)

• 1 \le t \le 100
• 1 \le n \le 8

Osatehtävä 2 (71 pistettä)

• 1 \le t \le 100
• 1 \le n \le 100