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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
import sys

# Povekszony limit rekursji dla glębokich gałęzi z DFS
sys.setrecursionlimit(20000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    t = int(input_data[0])
    idx = 1
    out =[]
    
    for _ in range(t):
        n = int(input_data[idx])
        idx += 1
        
        adj = {i: set() for i in range(1, n + 1)}
        for _ in range(n - 1):
            u = int(input_data[idx])
            v = int(input_data[idx+1])
            idx += 2
            adj[u].add(v)
            adj[v].add(u)
            
        IDs = [0] * (n + 1)
        memo = {}
        
        # Funkcja pomocnicza generująca jednoznaczny podpis (hash) izomorficznych fragmentów lasu
        def get_signature(u, p, current_adj, current_IDs):
            child_sigs =[]
            for v in current_adj[u]:
                if v == p: continue
                if current_IDs[v] > 0:
                    child_sigs.append(f"S{current_IDs[v]}")
                else:
                    child_sigs.append(get_signature(v, u, current_adj, current_IDs))
            child_sigs.sort()
            return "(" + "".join(child_sigs) + ")"
            
        def dfs(current_adj, current_IDs, c):
            current_adj = {u: set(v) for u, v in current_adj.items()}
            current_IDs = list(current_IDs)
            code =[]
            
            while True:
                # Kod kończy się, gdy zostaną tylko dwa wierzchołki w drzewie.
                if len(current_adj) <= 2:
                    return code
                    
                # ZASADA 1
                leaf_seen =[u for u in current_adj if len(current_adj[u]) == 1 and current_IDs[u] > 0]
                        
                if leaf_seen:
                    u = min(leaf_seen, key=lambda x: current_IDs[x])
                    neighbor = list(current_adj[u])[0]
                    current_adj[neighbor].remove(u)
                    del current_adj[u]
                    if current_IDs[neighbor] == 0:
                        current_IDs[neighbor] = c
                        c += 1
                    code.append(current_IDs[neighbor])
                    continue
                    
                # ZASADA 2
                seen_with_leaves = []
                for u in current_adj:
                    if current_IDs[u] > 0:
                        for v in current_adj[u]:
                            if len(current_adj[v]) == 1 and current_IDs[v] == 0:
                                seen_with_leaves.append(u)
                                break
                                
                if seen_with_leaves:
                    u = min(seen_with_leaves, key=lambda x: current_IDs[x])
                    leaf = None
                    for v in current_adj[u]:
                        if len(current_adj[v]) == 1 and current_IDs[v] == 0:
                            leaf = v
                            break
                    current_adj[u].remove(leaf)
                    del current_adj[leaf]
                    code.append(current_IDs[u])
                    continue
                    
                # ZASADA 3
                Cand =[]
                for u in current_adj:
                    if current_IDs[u] == 0:
                        leaves = sum(1 for v in current_adj[u] if len(current_adj[v]) == 1 and current_IDs[v] == 0)
                        if leaves > 0:
                            Cand.append((u, leaves))
                            
                best_key = None
                best_candidates =[]
                
                for u, k in Cand:
                    deg_prime = len(current_adj[u]) - k
                    if deg_prime == 1:
                        Q = None
                        for v in current_adj[u]:
                            if not (len(current_adj[v]) == 1 and current_IDs[v] == 0):
                                Q = v
                                break
                        if current_IDs[Q] > 0:
                            key = (1, k, current_IDs[Q]) # Kandydat Typu 1 
                        else:
                            key = (2, -k, 0)             # Kandydat Typu 2
                    else:
                        key = (2, -k, 0)
                        
                    if best_key is None or key < best_key:
                        best_key = key
                        best_candidates = [u]
                    elif key == best_key:
                        best_candidates.append(u)
                        
                if best_key[0] == 1:
                    u = best_candidates[0]
                    current_IDs[u] = c
                    c += 1
                    continue
                    
                # Usuwanie izomorficznych redundancji przy remisie Typu 2 
                sigs = {}
                for u in best_candidates:
                    sig = get_signature(u, -1, current_adj, current_IDs)
                    if sig not in sigs:
                        sigs[sig] = u
                        
                unique_cands = list(sigs.values())
                if len(unique_cands) == 1:
                    u = unique_cands[0]
                    current_IDs[u] = c
                    c += 1
                    continue
                    
                # Caching stanu aby zapobiec TLE przy gałęziach
                edges = []
                for x in current_adj:
                    for y in current_adj[x]:
                        if x < y:
                            edges.append((x, y))
                state_hash = (tuple(sorted(edges)), tuple(current_IDs))
                if state_hash in memo:
                    return code + memo[state_hash]
                    
                unique_cands.sort(key=lambda u: get_signature(u, -1, current_adj, current_IDs))
                
                best_sub_code = None
                for u in unique_cands:
                    sub_IDs = list(current_IDs)
                    sub_IDs[u] = c
                    sub_code = dfs(current_adj, sub_IDs, c + 1)
                    if best_sub_code is None or sub_code < best_sub_code:
                        best_sub_code = sub_code
                        
                memo[state_hash] = best_sub_code
                return code + best_sub_code

        res = dfs(adj, IDs, 1)
        out.append(" ".join(map(str, res)))
        
    print("\n".join(out))

if __name__ == '__main__':
    solve()