Loading...
$N$개의 정수로 이루어진 차수 수열이 주어진다. 이 차수 수열을 갖는 단순 그래프(무방향 그래프이며, 자기 간선과 다중 간선이 없는 그래프)를 구성하라. 구성이 불가능하다면 -1을 출력하라.
차수 수열이 단순 그래프로 구성 가능한지 판별하기 위해 Erdős-Gallai 정리를 활용하라. Erdős-Gallai 정리에 따르면, 차수 수열을 내림차순으로 정렬한 $d_1 \ge d_2 \ge \dots \ge d_N$에 대해 모든 $k$ ($1 \le k \le N$)에 대하여 다음 부등식을 만족하는 경우에만 단순 그래프로 구성할 수 있다.
$$ \sum_{i=1}^{k} d_i \le k(k-1) + \sum_{i=k+1}^{N} \min(d_i, k) $$
첫째 줄에 정점의 수 $N$이 주어진다.
둘째 줄에 각 정점의 차수를 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다.
주어진 차수 수열로 단순 그래프를 구성할 수 있다면, 첫째 줄에 간선의 수 $M$을 출력한다. 둘째 줄부터 $M$개의 줄에 걸쳐 각 간선의 양 끝 정점 번호 $u$와 $v$를 공백으로 구분하여 출력한다. 간선의 출력 순서와 정점의 출력 순서는 상관없다. 모든 정점의 차수가 0이어서 간선이 하나도 없는 경우, 첫째 줄에 0만 출력한다.
그래프를 구성할 수 없다면 첫째 줄에 -1을 출력한다.
4
3 3 3 3
6
1 2
1 3
1 4
2 3
2 4
3 4
3
3 2 1
-1