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

public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入，使用PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取测试用例数量T
        int T = Integer.parseInt(br.readLine().trim());

        // 处理每个测试用例
        while (T-- > 0) {
            // 读取树的节点数n
            int n = Integer.parseInt(br.readLine().trim());
            // 创建邻接表表示树
            List<Integer>[] adj = new ArrayList[n + 1];
            // 初始化邻接表
            for (int i = 1; i <= n; i++) {
                adj[i] = new ArrayList<>();
            }
            // 创建度数数组
            int[] deg = new int[n + 1];

            // 读取n-1条边，构建邻接表和度数数组
            for (int i = 0; i < n - 1; i++) {
                String[] edge = br.readLine().trim().split("\\s+");
                int u = Integer.parseInt(edge[0]);
                int v = Integer.parseInt(edge[1]);
                // 无向图，双向添加边
                adj[u].add(v);
                adj[v].add(u);

                // 更新节点的度数
                deg[u]++;
                deg[v]++;
            }
            // 创建距离数组，初始化为-1
            int[] dist = new int[n + 1];
            Arrays.fill(dist, -1);
            // 创建队列用于BFS
            Queue<Integer> queue = new LinkedList<>();

            // 将所有度为1的节点（叶子节点）加入队列，距离设为0
            for (int i = 1; i <= n; i++) {
                if (deg[i] == 1) {
                    dist[i] = 0;
                    queue.add(i);
                }
            }

            // BFS遍历树，计算每个节点到最近叶子节点的距离
            while (!queue.isEmpty()) {
                int u = queue.poll();
                // 遍历当前节点的所有邻接节点
                for (int v : adj[u]) {
                    if (dist[v] == -1) {
                        // 更新距离并加入队列
                        dist[v] = dist[u] + 1;
                        queue.add(v);
                    }
                }
            }

            // 找到最大距离
            int maxDist = -1;
            for (int i = 1; i <= n; i++) {
                // 只考虑非叶子节点
                if (deg[i] > 1) {
                    maxDist = Math.max(maxDist, dist[i]);
                }
            }

            // 收集所有距离为最大距离的非叶子节点（中心点）
            List<Integer> mikuPoints = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                if (deg[i] > 1 && dist[i] == maxDist) {
                    mikuPoints.add(i);
                }
            }

            // 输出中心点的数量
            out.println(mikuPoints.size());

            // 输出所有中心点
            for (int i = 0; i < mikuPoints.size(); i++) {
                out.print(mikuPoints.get(i) + (i == mikuPoints.size() - 1 ? "" : " "));
            }
            out.println();
        }

        // 刷新输出缓冲区，确保所有输出都被写入
        out.flush();
        // 关闭输出流
        out.close();
        // 关闭输入流
        br.close();
    }