광케이블을 대신하는 무선망

대역폭에 제한이 없는 새로운 무선 통신 방식이 시험을 통과했다. 늘어나는 트래픽을 감당하지 못하는 기존 광케이블 망을 이 방식으로 교체할 수 있다. 새 망의 배치는 당신이 정한다.

기존 망은 메시지를 중계하는 노드와, 서로 다른 두 노드를 잇는 광케이블 회선으로 이루어진다. 어느 두 노드 사이에도 광케이블을 따라가는 경로가 적어도 하나 있고, 대역폭 때문에 두 노드를 회선 여러 개가 잇기도 한다.

새 망에는 광케이블이 없다. 대신 두 노드를 잇는 무선 회선을 쓴다. 대역폭에는 제한이 없지만 무선 회선은 비싸다. 그래서 망 전체를 연결한 상태로 두면서 회선 수를 최소로 한다. 즉 어느 두 노드 사이에도 무선 회선을 따라가는 경로가 정확히 하나 있어야 한다. 한편 각 노드는 연결 개수를 미리 정해 두고 만들었다. 지금 연결된 회선 수와 다른 수의 회선에 연결되는 노드는 재구성해야 하고, 여기에 비용이 든다.

어느 두 노드 사이에도 경로가 정확히 하나씩 있으면서 회선 수가 기존 망과 달라지는 노드 수가 최소가 되도록 새 망을 설계하라.

첫째 줄에 노드 수 $n$과 기존 망의 광케이블 회선 수 $m$이 주어진다 ($2 \le n \le 10^4$, $1 \le m \le 10^5$). 노드 번호는 $0$부터 $n - 1$까지다.

다음 $m$개 줄에는 서로 다른 두 정수 $a_i$와 $b_i$가 주어진다. $i$번째 광케이블 회선이 노드 $a_i$와 노드 $b_i$를 잇는다는 뜻이다. 어느 두 노드 사이에도 광케이블 회선으로 이어지는 경로가 적어도 하나 있다. 두 노드를 광케이블 회선 여러 개가 이을 수도 있다.

첫째 줄에 회선 수를 바꿔야 하는 노드의 최소 개수를 출력한다.

둘째 줄에는 노드 수와 무선 회선 수를 출력한다. 노드 수는 입력과 같다. 이어지는 각 줄에는 무선 회선 하나를 두 노드 번호로 출력하되 작은 번호를 앞에 쓴다. 회선은 앞 번호 오름차순으로, 앞 번호가 같으면 뒤 번호 오름차순으로 정렬한다.

최소를 달성하는 배치가 여럿이므로 다음 절차가 만드는 배치를 출력한다. $d_v$를 기존 망에서 노드 $v$에 연결된 광케이블 회선 수라고 하자. 같은 두 노드를 잇는 회선이 여럿이면 각각 따로 센다.

1. 노드를 $d_v$ 오름차순으로, $d_v$가 같으면 번호가 작은 쪽을 앞에 두고 정렬한다. 합을 $0$에서 시작해 정렬한 순서대로 읽는다. 각 노드에서 $d_v - 1$을 더한 값이 $n - 2$ 이하이면 더하고, 합이 $n - 2$를 넘게 만드는 첫 노드에서 멈춘다. 멈추기 전까지 읽은 노드가 보존 노드다.
2. 보존 노드는 $t_v = d_v$로, 나머지 노드는 $t_v = 1$로 둔다. 보존되지 않은 노드가 하나라도 있으면 그중 번호가 가장 작은 노드 $w$의 $t_w$에 $2n - 2 - \sum_v t_v$를 더한다.
3. $n = 2$이면 무선 회선은 노드 $0$과 노드 $1$을 잇는 하나뿐이다. 그렇지 않으면 $t_v \ge 2$인 노드를 $v_1 < v_2 < \dots < v_p$, $t_v = 1$인 노드를 $u_1 < u_2 < \dots < u_L$이라고 하자. 먼저 경로 $v_1 v_2, v_2 v_3, \dots, v_{p-1} v_p$를 만든다. $v_i$의 남은 용량은 $t_{v_i}$에서 $v_i$에 이미 붙은 경로 회선 수를 뺀 값이다. $u_1, u_2, \dots, u_L$을 이 순서대로 남은 용량이 있는 첫 $v_i$에 붙인다. 즉 $v_1$의 남은 용량을 다 쓴 다음에 $v_2$가 노드를 받는다.

3단계는 항상 모든 $u_j$를 붙이고, 무선 회선 수는 항상 $n - 1$이다.