도로

뉴 아시아 왕국에는 $M$개의 도로로 연결된 $N$개의 마을이 있다. 어떤 도로는 자갈로, 다른 도로는 콘크리트로 포장되어 있다. 모든 도로를 무료로 유지하기에는 비용이 너무 많이 들기 때문에, 왕은 새로운 도로 유지 방안을 세우기로 했다.

왕은 무료 도로의 수를 최소로 하되, 어떤 마을에서 다른 마을로 갈 때 무료 도로만 이용하는 경로가 정확히 하나 존재하도록 하려고 한다. 즉, 무료 도로들은 모든 마을을 연결하는 하나의 트리를 이루어야 한다. 또한 왕은 자갈길을 걷는 것을 좋아하여, 무료 도로 중 자갈 도로가 정확히 $K$개가 되기를 원한다.

예를 들어 뉴 아시아 왕국의 마을과 도로가 그림 1a와 같다고 하자. 왕이 자갈 도로 $2$개를 무료로 하고자 한다면, 그림 1b와 같이 도로 $(1, 2), (2, 3), (3, 4), (3, 5)$를 무료로 하는 방안이 조건을 만족한다. 이 방안은 (1) 모든 마을이 무료 도로로 연결되고, (2) 무료 도로의 수가 가능한 한 적으며, (3) 무료 자갈 도로가 정확히 두 개, 즉 $(2, 3)$과 $(3, 4)$이기 때문이다. 따라서 이 경우에는 조건을 만족하는 방안이 존재하므로 답은 possible이다.

그림 1: (a) 뉴 아시아 왕국의 마을과 도로 예시. 실선은 콘크리트 도로를, 점선은 자갈 도로를 나타낸다. (b) 무료 자갈 도로가 정확히 두 개인 도로 유지 방안. 무료 도로만 표시하였다.

왕국의 도로와 왕이 원하는 무료 자갈 도로의 수 $K$가 주어질 때, 왕의 요구를 만족하는 도로 유지 방안이 존재하는지 판정하는 프로그램을 작성하라.

첫 줄에 세 정수가 공백으로 구분되어 주어진다.

• $N$: 마을의 수 ($1 \le N \le 20,000$)
• $M$: 도로의 수 ($1 \le M \le 100,000$)
• $K$: 왕이 무료로 유지하려는 자갈 도로의 수 ($0 \le K \le N-1$)

다음 $M$개의 줄에는 도로가 $1$번부터 $M$번까지 기술된다. $(i+1)$번째 줄은 도로 $i$를 나타내며, 공백으로 구분된 세 정수가 주어진다.

• $u_i$와 $v_i$: 도로 $i$가 연결하는 두 마을 (마을은 $1$부터 $N$까지 번호가 매겨진다)
• $c_i$: 도로 $i$의 종류. $c_i = 0$은 자갈 도로, $c_i = 1$은 콘크리트 도로를 뜻한다.

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

왕의 요구를 만족하는 도로 유지 방안이 존재하면 possible을, 존재하지 않으면 no solution을 한 줄에 출력한다.