30707번 - 스패닝 최소 트리 스페셜 저지

그래프의 스패닝 트리란, 그래프의 모든 정점이 서로 연결되어 있고 사이클이 없는 부분 그래프를 뜻한다. 그래프의 스패닝 트리들 중 간선들의 가중치의 합이 최소가 되는 것을 그 그래프의 최소 스패닝 트리라고 한다. 그래프에서 최소 스패닝 트리를 구하는 대표적인 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다.

이제 아래의 조건을 만족하는 그래프 $G$를 하나 찾아서 출력해보자.

• 그래프 $G$는 $N$개의 정점, $M$개의 간선으로 이루어진 그래프이다.
• 그래프 $G$에는 자기 자신을 연결하는 간선(self-loop)이 없으며, 임의의 서로 다른 두 정점 사이를 잇는 간선은 최대 하나 존재한다.
• 그래프 $G$의 각 간선에는 가중치가 있으며, $1\leq i\leq M$을 만족하는 모든 정수 $i$에 대해 가중치가 $i$인 간선이 정확히 한 개 존재한다.
• 그래프 $G$의 최소 스패닝 트리의 간선 가중치 합이 $S$이다.

첫 번째 줄에 세 양의 정수 $N$, $M$, $S$가 공백으로 구분되어 주어진다. ($2\leq N\leq 100\,000;$ $N-1\leq M\leq\min\left({{N(N-1)}\over{2}} ,10^6\right);$ $1\leq S\leq 10^{12}$)

입력으로 주어진 $N,M,S$에 대하여 주어진 조건을 만족하는 그래프 $G$가 존재하면 $M$개 줄에 걸쳐 조건을 만족하는 그래프의 간선들을 출력한다. $i(1\leq i\leq M)$번째 줄에는 가중치가 $i$인 간선이 연결하는 두 정점의 번호 $u_i$, $v_i$($1\leq u_i,v_i\leq N$)를 공백으로 구분하여 출력한다. (정점 번호의 순서는 상관없다.)

조건을 만족하는 그래프 $G$가 여러 개 존재한다면 그 중 하나를 아무거나 출력한다.

만일 조건을 만족하는 그래프 $G$가 없다면 첫 번째 줄에 -1을 출력한다.

어떤 그래프의 정점과 간선 일부로 이루어진 그래프를 그 그래프의 부분 그래프라고 한다.