그래프 복원

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

$N$개의 정점, $M$개의 간선으로 이루어진 그래프가 있다. 그래프의 정점 번호는 $1, 2, \cdots , N-1, N$이다. 이 그래프의 모양은 대신이만 볼 수 있고 오량이는 볼 수 없다. 오량이가 주어진 그래프의 모양을 복원해내면 성공하며, 그렇지 못하면 실패한다.

대신이는 오량이에게 몇 개의 메시지를 보낼 수 있으며, 대신이가 $i$번째로 보낸 메시지는 다음과 같다.

$u_i\ v_i$

이때, $u$와 $v$는 그래프의 두 정점이다. 이때, 오량이가 $i$번째로 전달받는 메시지는 다음과 같다.

$u_i \ v_i \ c_i$

$c_i$는 그래프에서 $u_i$와 $v_i$를 잇는 경로 중에 가장 짧은 것의 길이를 의미한다. 만약 그러한 경로가 없을 경우 $c_i$는 $-1$이 된다.

메시지를 너무 많이 보내면 게임이 지루해질 수 있으므로, 최대 $80$개의 메시지만으로 게임을 성공시키려고 한다.

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

대신이의 전략을 구성해야 할 때의 입력은 다음과 같다.

첫번째 줄에 $0$이 주어진다. 이는 해당 입력에서 대신이의 전략을 구성해야 함을 의미한다.

두번째 줄에 정점의 수 $N$, 간선의 수 $M$이 공백으로 구분되어 주어진다.

세번째 줄부터 $M$개의 줄에 걸쳐, 그래프의 간선 정보를 나타내는 $u_i$, $v_i$가 공백으로 구분되어 주어진다. 이는 그래프에서 $u_i$와 $v_i$가 서로 연결되어 있음을 의미한다.

---

오량이의 전략을 구성해야 할 때의 입력은 다음과 같다.

첫번째 줄에 $1$이 주어진다. 이는 해당 입력에서 오량이의 전략을 구성해야 함을 의미한다.

두번째 줄에 정점의 수 $N$, 대신이가 보낸 메시지의 개수 $Q$가 공백으로 구분되어 주어진다.

세번째 줄부터 $Q$개의 줄에 걸쳐, $u_i$, $v_i$, $c_i$가 공백으로 구분되어 주어진다. 이는 대신이가 $i$번째로 보낸 메시지가 $u_i$, $v_i$이며, 이 두 정점 사이의 거리는 $c_i$임을 의미한다.

대신이의 전략을 구성했을 때의 출력은 다음과 같다.

첫번째 줄에 보낼 메시지의 개수 $Q$를 출력한다.

두번째 줄부터 $Q$개의 줄에 걸쳐, $i$번째 메시지에 전달할 2개의 정점 $u_i$, $v_i$를 공백으로 구분해 출력한다.

---

오량이의 전략을 구성했을 때의 출력은 다음과 같다.

첫번째 줄에 복원한 그래프의 간선 개수 $M$을 출력한다.

두번째 줄부터 $M$개의 줄에 걸쳐, 그래프에서 간선을 통해 이어진 두 정점 $u$와 $v$를 공백으로 구분해 출력한다. 가능한 출력이 여러 개라면, 그 중 아무거나 하나를 출력한다.

$N = 40$

$0 \le M \le 780$

어떤 간선의 양 끝점이 같은 경우는 없으며, 어떤 두 정점에 대해서도 그 두 점을 잇는 간선은 최대 하나이다.

전달하는 메시지는 모두 $1 \le u_i \le N$, $1 \le v_i \le N$ ($1 \le i \le Q$)를 만족해야 한다.