문제

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

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

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

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

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

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

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

입력

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

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

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

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

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

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

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

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

출력

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

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

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

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

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

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

노트

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

전달하는 메시지는 모두 , ()를 만족해야 한다.

예제 설명

예제 입력은 이해를 돕기 위한 것이며, 이므로 실제 테스트케이스에서는 주어지지 않는다.

예제 첫 번째는, 첫 줄에 이 주어지므로 대신이의 전략을 구성해야 한다.

입력되는 그래프의 형태는 다음과 같다.

예제 두 번째는, 첫 줄에 이 주어지므로 오량이의 전략을 구성해야 한다.