Problem : 231 - Roads

Special Judge

Problem Statistics

Solved Member: 15　　Submission: 71　　User Tried: 15

Statement:

新亞洲王國內共有M條道路連結N個村莊。有些道路是鵝卵石路，有些則是混凝土路。要保持所有道路免收費使用就需要龐大的支出，因此這似乎是不可能的。所以王國需要一個新的道路維護計畫。

國王最終決定要保留越少道路越好，但是每兩個不同的村莊之間一定要要保留一條，且只有一條，免費的路徑。此外，雖然混凝土路比較符合現今道路需求，國王認為走在鵝卵石路上是比較有趣的，因此他決定恰好要保留K條免費的鵝卵石路。

舉例來說，假設新亞洲王國的村莊與道路如圖1(a)所示，如果國王要保留兩條免費的鵝卵石路，那就可以如圖1(b)將道路 (1, 2), (2, 3), (3, 4) 和 (3, 5) 保留為免費通行。此安排符合國王的要求因為 (1)每兩個村莊之間都有一條免費路徑，(2)免費道路越少越好，(3) 所有免費道路中剛好有兩條鵝卵石路，即 (2, 3) 和 (3, 4)。

圖1：
(a)新亞洲王國村莊與道路範例。實線代表混凝土路，虛線代表鵝卵石路。
(b)一個含有兩條免費鵝卵石路的道路維護計畫，圖中只畫出免費道路。

Task:

給定新亞洲王國的道路圖，與國王所想要保持免費的鵝卵石路數量，請寫一個程式來判斷是否有可以符合國王要求的道路維護計畫，如果有，請輸出該計畫。

Input:Output:

第一行有三個整數N M K，以空白隔開。
N，代表村莊數 (1 ≤ N ≤ 20,000)
M，代表道路數 (1 ≤ M ≤ 100,000)
K，代表國王要求保留免費的鵝卵石路數量 (0 ≤ K ≤ N - 1)

接下來的M 行描述新亞洲王國的道路狀況，第 (i+1) 行代表道路i，道路編號以 1 到 M代表之。每一行都有三個以空白隔開的整數： ui 和 vi，代表道路i 連接村莊 ui 和 vi ，村莊以數字 1 到 N 代表之。 ci ，代表道路 i 的型態：若 ci = 0 則道路 i 是鵝卵石路；若 ci = 1 則道路 i 是混凝土路。

每兩個村莊之間不會有超過一個連接兩村莊的道路。

若是不可能有一個符合國王要求的道路維護計畫，則在第一行輸出 no solution。否則，你的程式應該輸出一個可行的道路維護計畫中，該維持免費的道路。輸出的道路格式應與輸入資料中該道路的描述相同，輸出的道路可以以任何順序呈現。若是有一個以上符合要求的道路維護計畫，則只需要輸出其中一個即可。

Sample Input:Sample Output:

5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1

3 2 0
4 3 0
1 2 1
5 3 1

HINT:

範例輸入輸出如圖1所描述。

對於每組測試資料，如果輸出正確，就可得到 100% 的分數，否則就是 0% 的分數。此外，在共20分的測試資料組別中，K值最大為10。

2015/01/06 Special Judge Fixed. by bigelephant29

Source:

APIO 2008

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1-1	1000ms	131072kb	10
1-2	1000ms	131072kb
2-1	1000ms	131072kb	10
2-2	1000ms	131072kb
3	1000ms	131072kb	10
4	1000ms	131072kb	10
5	1000ms	131072kb	10
6	1000ms	131072kb	10
7	1000ms	131072kb	10
8	1000ms	131072kb	15
9	1000ms	131072kb	15