聖瑪格諾利亞共和國是一個規模龐大的國家,由 $N$ 個行政區組成,並且有 $N-1$ 條連接行政區與行政區的道路,讓任意兩個行政區都能互相往來。
由於最近國勢動盪,大總統為了防止鞏固勢力,決定重新劃分領土。他打算封鎖一些行政區,並且將每一個沒有被封鎖的行政區都指派到某個領域的管轄之內,使得任兩個屬於不同領域的行政區之間都沒有直接連接彼此的道路。
大總統命令你來決定要封鎖哪些行政區以及如何劃分各個領域。當然,這份差事沒有這麼簡單,他還給了你一個額外的要求:每一個行政區都有一個神秘的標記 $c_i$,當某一個行政區被選擇要封鎖時,其他與它擁有相同標記且距離為偶數的行政區也必須被選上。距離的定義是兩個行政區之間最少需要經過幾條道路才能到達,與中間的行政區是否被封鎖無關。
為了給出一個能讓大總統滿意的規劃,在滿足要求的方案之中,請找到任意一個包含最多領域的方式。
輸入第一行為一個整數 $N$,代表行政區的數量。接下來的 $N-1$ 行,每行包含兩個以空格隔開的整數 $u_i, v_i$,代表有一條雙向的道路連接 $u_i, v_i$ 兩個行政區。最後一行包含 $N$ 個以空格隔開的整數 $c_1, c_2, \ldots, c_N$,$c_i$ 為第 $i$ 個行政區的標記。
請輸出兩行。第一行為一個整數,代表最多能有幾個領域。第二行先輸出一個整數 $K$,代表要被封鎖的行政區數量,再輸出 $K$ 個由小到大的整數,代表要封鎖的行政區,中間皆以空格隔開。
當有多種滿足要求的選擇能讓領域數量最多時,可以輸出任意一組解。
如果你的第一行輸出正確,並且在第二行只輸出一個整數 $-1$,你將獲得一半的分數。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0 | 範例測資 | 0 |
2 | 0~53 | 無額外限制 | 100 |