領主進軍
問題敘述
Sakinu 最近迷上了一款名叫 TOOR 的桌遊，特別喜歡群鼠領主這個角色，陶醉於霸
道領主一雙大耳朵還有性感的長尾巴，他獨特的技能”領主進軍”更是讓人難以自拔。
TOOR 是在一張大地圖上遊玩，地圖可以視為一棵有N 個節點的樹，由編號0的領
地為根。
你總共有2×(N−1)個軍團，戰力為0∼2×(N−1)−1的軍團各恰有一個，且每
個領地的每條道路上都必須一個軍團駐守，所以每條道路上都會有兩個軍團，分別駐守
那條道路兩端的領地。
發動領主進軍時，領主選擇一塊起始領地，並選擇一條行軍路徑，這條行軍路徑不
能有重複的道路，獲得該條路徑上第一個碰到的軍團，也就是起始領地上負責駐守行軍
路徑中第一條道路的軍團。
之後領主沿行軍路徑開始移動，從A領地沿著道路X移動到B領地時，需要和B
領地負責駐守道路X的軍團比較戰力，如果領主指揮的軍團戰力大於B領地負責駐守道
路X的軍團的戰力，則領主可以到達B領地並繼續行軍，否則無法通過。
如果存在一個領地S，無論領主選擇任何領地S以外的起始領地與任何行軍路徑都
無法到達，則我們說領地S是無敵的。
現在地圖上有一些領地的某些道路上已經有軍團了，而有些領地，其周圍的道路你
還沒有軍團駐守，且你手上還有一些尚未安排駐守位置的軍團，由於Sakinu每次快要贏
的時候就會一直發出WOO∼之類的聲音，導致領居不勘其擾，貼了一張寫著請勿喧嘩
的紙條在他的住處門上，為了不讓Sakinu變成離家少女，請你安排剩下的每個軍團的駐
守位置，使無敵的領地數盡可能多。
輸入說明
第一行輸入一個正整數N，表示地圖上共有N 個領地，有N−1條道路，有戰力為
0 ∼2×(N −1)−1 的軍團各一個。
接下來共輸入N 行，第i行的第一個整數pi，表示接著有pi個整數，表示編號i的
子節點們的編號。
1
接下來共輸入N行，第i行的第一個整數qi，表示接著有qi個整數，皆為正整數或
是’-1’，表示編號i的節點相連的道路上駐守的軍團的戰力值，最先輸入與父節點相連的
道路上的軍團的戰力值(如果有父節點)，接著依道路另一端的子節點的編號，由小到大
輸出對應道路上的軍團的戰力，若為”-1”則表示對應位置尚無軍團駐守。
測試資料範圍
•3≤N≤105。
•∑qi=2×(N−1)。
輸出說明
輸出共包含N行。
第i行包含xi個整數，xi為與編號i的領地之間有道路相連的領地數量，最先輸
出與父節點相連的道路上的軍團的戰力值(如果有父節點)，接著依道路另一端的子節
點的編號，由小到大輸出對應道路上的軍團的戰力，這i行的所有整數必須介於0∼
2×(N−1)−1，且範圍內的所有整數必須恰出現一次，意義如題序所敘，如果有多種安
排方式均能使無敵的節點數達到可能的最大值，選擇使輸入中越早被輸入的”-1”對應位
置的軍團戰力最小的解。
範例測資
範例輸入1
3
212
0
0
20-1
11
1-1
範例輸出1
02
1
3
2
輔助說明
範例測資前四行表示樹的結構，最後三行分別表示三個節點周圍的軍團狀況
倒數第三行表示0號節點周圍的狀況，該行第一個整數表示其周圍有兩個軍團。0號
節點(根節點)周圍第一個軍團位在與其編號最小的子節點(1號節點)相連的邊上，該軍
團戰力為0，第二個軍團位在與2號節點相連的邊上，你可以從尚未出現的軍團中(戰力
為2或3的軍團)自由安排。
倒數第二行表示編號為1的節點周圍的軍團，該行第一個整數表示其周圍有一個軍
團。1 號節點不是根節點，所以周圍第一個軍團是與根節點相連的邊上的軍團，戰力為
1，由於此節點周圍只有一個軍團，此行到此結束。
最後一行意義與倒數第二行類似。
可以證明範例測資中最多只會有一個無敵的節點，所以我們需要選擇使越先被輸入
的”-1” 對應位置的軍團戰力最小的安排方式，第一種是將戰力為2的軍團分配給0號節
點與2號節點相連的邊上，若採用別種方式安排，第一個被輸入的”-1”對應的位置軍團
戰力不可能更小。
故需輸出:
0 2
1
3
3 |
