🧭 題目名稱：防禦塔的最佳落點

📝 題目描述：

在一片尚未完全開發的土地上，村落之間會逐步建立聯絡道路，這些道路形成一棵動態生成的無環連通圖（樹）。國王計劃在每次道路連接後，都在整體村落網路中選擇一個「最佳落點」來建造防禦塔，以保護整體網絡的穩定。

防禦塔的選址原則是：選擇目前整棵村落網絡中的重心節點。一個節點是重心，若移除它後，每個子網絡的節點數都不超過整體節點數的一半。若有多個符合條件的節點，選擇編號最小的那一個。

你的任務是，在每次新建一條道路後，輸出目前網絡的重心節點編號。

🌐 題目背景設定（遊戲主題）：

• 村落 = 節點
• 道路 = 邊
• 每次建造防禦塔 = 找重心
• 防禦塔會派出弓箭手進行巡邏，因此需放在「最平衡」的點，確保不會有任何一處村落太遠，來不及應援。

📥 輸入格式：

• 第一行一個整數 n（2 ≤ n ≤ 10⁵），代表村落數量。
• 接下來 n−1 行，每行兩個整數 u v（1 ≤ u,v ≤ n），表示第 i 天建立了一條從村落 u 到村落 v 的道路。

這些邊將構成一棵動態生成的樹。

📤 輸出格式：

• 輸出 n−1 行，每行一個整數，表示當天建好道路後應設立防禦塔的最佳節點（即重心）。

📘 輸入範例：

5
1 2
2 3
3 4
4 5

📗 輸出範例：

1
2
2
3

🎮 圖示說明：

每天新增一條邊後，村落網絡逐步變成：

1. 1-2 → 節點：1,2 → 重心是 1
2. 1-2-3 → 重心是 2
3. 1-2-3-4 → 重心仍為 2
4. 1-2-3-4-5 → 重心是 3

🔧 資料限制：

• 2 ≤ n ≤ 10⁵
• 邊的加入順序保證圖始終為一棵樹