놀라운 트리

무방향 트리가 주어진다. 다음 알고리즘은 트리의 후위 순회(post-order)를 만든다:

fun dfs(v):
    mark v as used
    for u in neighbours(v):
        if u is not used:
            dfs(u)
    append v to order

후위 순회 결과는 리스트 order에 담긴다. 각 정점의 이웃을 방문하는 순서와 시작 정점을 자유롭게 고를 수 있다. 얻을 수 있는 order 중 사전순으로 가장 작은 것을 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10^{5}$)가 주어진다. 각 테스트 케이스의 첫 줄에는 정점의 수 $n$ ($2 \le n \le 2 \cdot 10^{5}$)이 주어진다. 이어지는 $n-1$개의 줄에는 각각 두 정수 $u_i, v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$)가 주어지며, 이는 $u_i$와 $v_i$를 잇는 무방향 간선을 뜻한다. 주어진 그래프는 트리이다. 모든 테스트 케이스의 $n$을 합하면 $2 \cdot 10^{5}$을 넘지 않는다.

각 테스트 케이스마다 사전순으로 가장 작은 order를 한 줄에 출력한다.

첫 번째 테스트는 다음과 같다:

정점 1에서 시작하면 2 3 1 순서만 얻을 수 있다. 정점 2에서 시작하면 1 3 2 순서만 얻을 수 있다. 정점 3에서 시작하면 1 2 3과 2 1 3 두 가지 순서를 얻을 수 있다. 네 가지 순서 중 사전순으로 가장 작은 것은 1 2 3이다.

두 번째 테스트는 다음과 같다:

정점 1에서 시작하면 2 3 1과 3 2 1 두 가지 순서를 얻을 수 있다. 정점 2에서 시작하면 3 1 2 순서만 얻을 수 있다. 정점 3에서 시작하면 2 1 3 순서만 얻을 수 있다. 네 가지 순서 중 사전순으로 가장 작은 것은 2 1 3이다.

세 번째 테스트는 다음과 같다:

사전순으로 가장 작은 순서는 4 5 2 1 6 3 7이며, 정점 7에서 시작하면 얻을 수 있다.