204. 樹重心

給定一棵樹，如果把樹上的某一個節點及其所連的邊移除，我們會得到若干棵樹。例如下左圖為原始的樹，移除節點 $2$ 之後就會變成如中間那張圖，而若移除節點 $1$ 則會變成如右邊那張圖。

對於給定的一棵樹，我們定義拔除節點 $x$ 的慘度為「拔除節點 $x$ 後，形成的若干棵樹分別的節點數量中的最大值。」。舉例來說，上左圖拔除節點 $2$ 之後，形成 $2$ 棵樹，節點數量分別是 $1$ 和 $3$，其中最大者為 $3$，因此該樹拔除節點 $2$ 的慘度為 $3$。同理，該樹拔除節點 $1$ 的慘度為 $2$。

對於一棵樹，我們定義所有點當中，拔除它的慘度最小的點為「重心」。現在給你一棵樹，請你找出它的「重心」。

輸入說明

第一行為一個正整數 $T$，$T \le 10$，表示共有幾筆測試資料。

每筆測試資料的第一行為一個正整數 $N$，表示這棵樹共有 $N$ 個節點，編號為 $0$ 到 $N-1$。接續 $N-1$ 行，每行兩個整數 $a,b$，表示節點 $a$ 和節點 $b$ 有一條邊相連。

• 對於 $40\%$ 的測試資料，$N \le 100$
• 對於 $100\%$ 的測試資料，$2 \le N \le 10^5$、輸入為合法的一棵樹

輸出說明

對於每筆測試資料輸出一行，包含一個整數，即為這棵樹的重心的編號，若有多個，請輸出編號較小的。

範例輸入

1 5 0 1 1 2 1 4 2 3

範例輸出

1

範例說明

範例即為題目中的圖片，拔除節點 $0$ 的慘度為 $4$、拔除節點 $1$ 的慘度為 $2$、拔除節點 $2$ 的慘度為 $3$、拔除節點 $3$ 的慘度為 $4$、拔除節點 $4$ 的慘度為 $4$，拔除節點 $1$ 的慘度最小，因此答案為 $1$。

Judge Setting

run-time limit: 400 ms
memory limit: 5120000 byte
測資數量: 0