樹的重心（沿重子節點走）

題目敘述

假設一個社團的幹部之間有一套層層回報的聯絡網，它恰好是一棵樹。給定一棵有 n 個頂點的樹，頂點編號為 1 到 n。若以某個頂點為根，其所有子樹的大小都不超過 n/2，這個頂點就稱為重心。一棵樹可能有一個或兩個重心。

為了讓答案唯一，請依下列方式尋找：以頂點 1 為根，並令 u=1。只要 u 有某個子節點，其子樹大小嚴格大於 ⌊ n/2 ⌋，就移動到該子節點（這樣的子節點至多一個）；否則停止。最後停下的 u 就是答案。

輸入格式

• 第一行有一個整數 n。
• 接下來 n−1 行，每行有兩個整數，表示樹上的一條邊。

輸出格式

輸出一個整數，即上述走法停下的頂點。

限制

• 2 ≤ n ≤ 200

範例

範例 1

輸入

4
1 2
2 3
2 4

輸出

2

範例 2

輸入

2
1 2

輸出

1

說明

範例中以 1 為根時，頂點 2 的子樹大小為 3，大於 ⌊ 4/2 ⌋ = 2，所以走到 2；2 的子節點子樹大小都是 1，於是停在 2。