In 17th century our Chef was a Wizard. He asked his small son "Anshu" to bring him the secret of the Magical Mountain. The boy after travelling a lot reached the Mountain.

The description of the Mountain was as follows:
- Mountain contains N magical stones. Each of them has a unique number.
- Mountain was divided into many levels, where at ith level atmost 2^i stones can be found.
- Between stones there exist a magical path containing lava.
- A stone can be connected with maximum of three stones.
- Peak of the mountain contains stone with number 1.
- If Stone 1 is first connected to stone 2 and then to 3. Assume 2 is to the left of 3.

Now, to get the secret of the mountain, Anshu started climbing from the left. On the way he used his magical wand to protect him from lava. But, while climbing he came to know that he is able to see only the one stone at each level. After reaching the peak he slided down and did the the same process. These stones that he saw shows the secret of the mountain, if they are placed in a non decreasing order on a sunny day. Anshu doesn't remember the stones number that he saw. Help him in recollecting them and getting the secret to his father.

The mountain looks like this

-----Input-----
- First line contains T the number of test cases.
- First line of each test test case contains N.
- Next N-1 lines contains X and Y the stones which are connected.

-----Output-----
- Output the required non decreasing sequence.

-----Constraints and Subtasks-----
- 1 <= T <= 10
- 1 <= X, Y <= N
Subtask 1: 20 points
- 3<=N<=100
Subtask 2: 30 points
- 3<=N<=10000
Subtask 3: 50 points
- 3<=N<=100000

-----Example-----
Input:
1
5
1 2
1 3
2 4
2 5

Output:
1 2 3 4 5

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "for t in range(eval(input())):\n  \n  n = eval(input())\n  \n  a = [ [] for i in range(n+1) ]\n  \n  for i in range(n-1):\n    x,y = list(map( int, input().split() ))\n    a[x].append(y)\n    a[y].append(x)\n  \n  vis = [0] * (n+1)\n  vis[1] = 1\n\n  ans = [1]\n\n  t1 = [1]\n  t2 = []\n  \n  while len(t1) > 0 :\n    for u in t1:\n      for x in a[u]:\n        if vis[x] == 0 :\n          vis[x] = 1\n          t2.append(x)\n    if len(t2) > 1 :\n      ans.append(t2[0])\n      ans.append(t2[-1])\n    if len(t2) == 1 :\n      ans.append(t2[0])\n    \n    t1 = t2\n    t2 = []\n  \n  for x in sorted(ans):\n    print(x, end=' ')\n  \n  print('')"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18025