4014번 - 도로 스페셜 저지

뉴 아시아 왕국에는 M개의 도로로 연결된 N개의 마을이 있다. 어떤 도로들은 자갈로, 그리고 다른 도로들은 콘크리트로 포장이 되어있다. 무료도로를 유지하기 위해서는 많은 경비가 필요하기 때문에 이 왕국에서 모든 도로를 무료화 하는 것은 불가능하여 보인다. 따라서 새로운 도로유지 방안이 필요하다. 

왕은 무료도로의 수를 가능한 한 최소화하되, 어떤 마을에서 다른 마을로 갈 때 반드시 오직 하나의 무료도로로 이루어진 경로가 있도록 결정하였다. 또한 콘크리트 도로가 현대 교통에 적합하지만, 왕은 자갈길을 걷는 것이 매우 흥미 있다고 생각하였다. 결과적으로 왕은 정확히 K개의 자갈도로를 무료도로로 유지하기로 결정하였다.

예를 들어 뉴 아시아 왕국의 마을과 도로는 그림 1a와 같다. 만일 왕이 2개의 자갈도로를 무료로 하고자 하면, 왕국은 그림 1b와 같이 (1, 2), (2, 3), (3, 4), (3, 5)를 무료로 하여야 한다. 이 계획은 왕의 요구사항을 만족하는데 그 이유는 (1) 모든 두 마을이 무료도로를 통하여 연결되어 있으며, (2) 가능한 가장 적은 수의 무료도로를 가지고 있고, (3) 정확히 두 개의 무료 자갈도로를 포함한다: (2, 3)과 (3, 4) 

그림1: (a) 뉴 아시아 왕국의 마을과 도로 예. 실선은 콘크리트 도로를 점선은 자갈도로를 뜻함. (b) 정확히 두 개의 무료 자갈도로를 포함하는 도로유지방안. 무료도로만 표시되었음.

뉴 아시아왕국의 도로와 왕이 원하는 무료자갈도로의 수가 주어졌을 때, 왕의 요구사항을 만족하는 도로유지방안이 있다면 그 방안을 출력하는 프로그램을 작성하는 것이다

첫 번째 줄에는 세 개의 정수가 하나의 빈칸을 사이에 두고 주어진다. 

• N, 마을의 개수 (1≤ N ≤20,000),
• M, 도로의 개수 (1≤ M ≤100,000), 그리고
• K, 왕이 무료로 유지하기를 원하는 자갈도로의 개수 (0≤ K ≤ N-1)

다음 M 줄에는 1에서부터 M까지의 도로가 기술된다. (i+1)번째 줄은 도로 i를 뜻한다. 여기에는 세 개의 정수가 하나의 빈칸을 사이에 두고 주어진다: 

• u_i와 v_i, 도로 i에 의해 연결되는 두 마을. 마을은 1부터 N으로 표시되며, 
• c_i는 도로 i의 종류; c_i = 0은 자갈 도로, c_i = 1은 콘크리트 도로를 뜻한다.

인접한 두 마을을 연결하는 도로는 하나뿐이다. 

만일 왕의 요구사항을 만족하는 도로유지방안이 없다면, 여러분의 프로그램은 no solution을 첫 번째 줄에 출력하여야 한다.

그렇지 않은 경우, 여러분의 프로그램은 유효한 도로유지방안의 무료도로들을 한 줄에 하나씩 열거하여 출력하여야 한다. 도로는 입력 시 주어진 형태로 출력이 되어야 하나, 도로의 순서는 어떤 순서라도 무방하다. 만일 유효한 도로유지방안이 여러 개가 있는 경우, 그 중 하나만 출력하면 된다.