Etäisyydet

• Time limit: 1.00 s
• Memory limit: 512 MB

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$