34988번 - 그래프 복원 투 스텝

문제

이 문제는 투 스텝 문제입니다.

대신이와 오량이는 그래프를 이용해 재밌는 게임을 하려고 한다. 게임의 규칙은 다음과 같다.

$N$개의 정점, $M$개의 간선으로 이루어진 무방향 단순 그래프가 있다. 각 정점에는 1ドル$부터 $N$까지의 번호가 매겨져 있으며 모든 간선의 길이는 1ドル$로 같다.

이 그래프의 모양은 대신이에게만 주어진다. 오량이가 대신이에게 주어진 그래프의 간선을 모두 알아내어 모양을 복원해 내면 승리하며 그렇지 못하면 패배한다. 대신이는 게임에서 승리하기 위해 오량이에게 최대 80ドル$개의 메시지를 보낼 수 있다. 메시지가 전달되는 과정은 아래와 같다.

• 대신이가 2ドル$개의 정점 $u, v$를 골라 메시지를 전송한다. 단, $u\neq v$일 필요는 없다.
• 오량이는 $u ,円 v ,円 c$ 형태의 메시지를 받는다. 이때, $c$는 $u$와 $v$를 잇는 최단 경로의 길이이며, 그러한 경로가 존재하지 않을 때에는 -1이다.

대신이와 오량이를 위해 게임에서 승리할 수 있는 전략을 구성해 보자!

입력

첫번째 줄에 전략의 종류를 나타내는 정수 $T$가 주어진다. $(T\in\{0,1\})$

$T=0$인 경우 당신은 대신이의 전략을 구성해야 한다. 두번째 줄에 정점의 수 $N,ドル 간선의 수 $M$이 공백으로 구분되어 주어진다. 세번째 줄부터 $M$개의 줄에 걸쳐, 그래프의 간선이 연결하는 두 정점의 번호 $u,ドル $v$가 공백으로 구분되어 주어진다. $(N=40;$ 0ドル \le M \le 780;$ 1ドル \le u,v \le N;$ $u \neq v)$

$T=1$인 경우 당신은 오량이의 전략을 구성해야 한다. 두번째 줄에 정점의 수 $N,ドル 대신이가 보낸 메시지의 개수 $Q$가 공백으로 구분되어 주어진다. 세번째 줄부터 $Q$개의 줄에 걸쳐, $u_i,ドル $v_i,ドル $c_i$가 공백으로 구분되어 주어진다. 이는 오량이가 $i$번째로 받은 메시지의 내용이 $u_i \ v_i \ c_i$임을 의미하며, 이는 대신이가 $i$번째로 보낸 메시지와 대응된다. $(N=40)$

출력

대신이의 전략을 구성했을 때, 즉 $T=0$일 때 첫번째 줄에 보낼 메시지의 개수 $Q$를 출력한다. 두번째 줄부터 $Q$개의 줄에 걸쳐, $i$번째 메시지에 전달할 2ドル$개의 정점 $u_i,ドル $v_i$를 공백으로 구분해 출력한다. $(1\le Q \le 80)$

오량이의 전략을 구성했을 때, 즉 $T=1$일 때 첫번째 줄에 복원한 그래프의 간선 개수 $M$을 출력한다. 두번째 줄부터 $M$개의 줄에 걸쳐, 그래프에서 간선을 통해 이어진 두 정점 $u$와 $v$를 공백으로 구분해 출력한다.

가능한 출력이 여러 개라면, 그중 아무거나 하나를 출력한다.

제한

노트