16950번 - 레드 블루 스패닝 트리 2 스페셜 저지

무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내고, 있으면 그 중 아무거나 하나를 출력하는 프로그램을 작성하시오.

첫 줄에는 세 정수 n, m, k가 주어진다. n은 그래프의 정점의 개수 (2 ≤ n ≤ 1,000)이고, m은 간선의 개수, k는 문제에 설명되어 있는 파란색 간선의 개수 (0 ≤ k < n) 이다.

다음 m개 줄에는 간선의 정보가 주어지며, 각 정보는 세 정수 c, f, t로 이루어져 있다. c는 간선의 색상을 나타내며, 빨간색인 경우에는 R, 파란색인 경우에는 B이다. f와 t는 정수로 간선이 연결하는 두 정점을 나타낸다. (1 ≤ f, t ≤ n, f ≠ t) 두 정점을 연결하는 간선은 최대 한 개이다.

파란색 간선이 정확하게 k개인 스패닝 트리를 만들 수 있으면 총 n-1개의 줄을 출력한다. 각 줄에 하나씩 한 간선의 양 끝점의 번호를 차례대로 출력한다.

조건을 만족하는 스패닝 트리를 만들 수 없으면 0을 출력한다.