1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import sys
import heapq

def rozwiaz_jeden(n, krawedzie):
    if n <= 2:
        return ""
    graf = [[] for _ in range(n+1)]
    stopien = [0]*(n+1)
    for a,b in krawedzie:
        graf[a].append(b)
        graf[b].append(a)
        stopien[a] += 1
        stopien[b] += 1
    usuniety = [False]*(n+1)
    pq = []
    def dodaj_lisc(v):
        u = -1
        for w in graf[v]:
            if not usuniety[w]:
                u = w
                break
        if u == -1:
            return
        heapq.heappush(pq, (stopien[u], u, v))
    for v in range(1, n+1):
        if stopien[v] == 1:
            dodaj_lisc(v)
    sasiad_przy_usunieciu = [0]*(n+1)
    etykieta = [0]*(n+1)
    krok = 0
    while krok < n:
        while pq:
            d_u, u, v = heapq.heappop(pq)
            if usuniety[v]:
                continue
            if stopien[v] != 1:
                continue
            aktualny_u = -1
            for w in graf[v]:
                if not usuniety[w]:
                    aktualny_u = w
                    break
            if aktualny_u != u:
                if aktualny_u != -1:
                    heapq.heappush(pq, (stopien[aktualny_u], aktualny_u, v))
                continue
            break
        else:
            break
        krok += 1
        usuniety[v] = True
        sasiad_przy_usunieciu[krok] = u
        etykieta[v] = krok
        stopien[u] -= 1
        if stopien[u] == 1:
            dodaj_lisc(u)
    kod = []
    for i in range(1, n-1):
        u = sasiad_przy_usunieciu[i]
        kod.append(str(etykieta[u]))
    return " ".join(kod)

def main():
    dane = sys.stdin.read().strip().split()
    if not dane:
        return
    it = iter(dane)
    t = int(next(it))
    out = []
    for _ in range(t):
        n = int(next(it))
        krawedzie = []
        for _ in range(n-1):
            a = int(next(it)); b = int(next(it))
            krawedzie.append((a,b))
        out.append(rozwiaz_jeden(n, krawedzie))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()