题目描述

一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。

当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，设该城市i的聚集度为DPi（Degree of Polymerization），DPi = max（城市群1的城市个数，城市群2的城市个数，…城市群m 的城市个数）。

请找出地图上DP值最小的城市（即找到城市j，使得DPj = min(DP1,DP2 … DPn))

提示：如果有多个城市都满足条件，这些城市都要找出来（可能存在多个解）

提示：DPi的计算，可以理解为已知一棵树，删除某个节点后；生成的多个子树，求解多个子数节点数的问题。

输入描述

每个样例：第一行有一个整数N，表示有N个节点。1 <= N <= 1000。

接下来的N-1行每行有两个整数x，y，表示城市x与城市y连接。1 <= x, y <= N

输出描述

输出城市的编号。如果有多个，按照编号升序输出。

用例

java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static class UnionFindSet {
        private int[] father; // 存储每个节点的父节点

        public UnionFindSet(int n) { // 初始化并查集，每个节点的父节点为自己
            father = new int[n];
            for (int i = 0; i < n; i++) father[i] = i;
        }

        public int find(int x) { // 查找x的祖先节点，路径压缩优化
            if (father[x] != x) {
                father[x] = find(father[x]);
            }
            return father[x];
        }

        public void unionSe