치노와 코코아

문제

이 문제는 한 번 채점할 때 참가자의 프로그램을 $2$ 번 실행하는 형식의 문제이다. 각 실행은 일반적인 문제와 같이 진행된다.

치노와 코코아는 리제의 훈련을 받고 있다. 그 훈련은 다음과 같이 구성된다.

치노에게 정점이 $N$ 개인 트리가 주어진다. 트리의 정점에는 $1$ 부터 $N$ 까지의 정수 번호가 붙어있으며, 트리의 루트는 $1$ 번 정점이다. 트리의 높이는 $10$ 을 넘지 않는다. 트리의 높이는 루트에서 어떤 정점까지의 경로에 포함된 간선의 개수의 최댓값이다.
치노는 정수 $K$ ( $K \ge \left\lfloor \frac{N^2}{5} \right\rfloor$ )를 원하는 수로 정한 뒤 $K$ 개의 간선을 트리에 추가하여 그래프를 만든다. 추가하는 간선은 기존의 트리에 존재하지 않아야 하며, 간선을 추가한 후의 그래프는 중복 간선을 가지면 안 된다.
코코아에게는 치노가 만든 그래프와 $K$ 가 주어진다. 그래프의 간선은 정렬되어 주어지며, 자세한 사항은 입력 형식에 설명되어 있다.
코코아는 치노가 처음에 받은 트리가 무엇인지 알아내야 한다.

치노와 코코아가 리제의 훈련을 무사히 마칠 수 있도록 도와주자!

입력

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

$T=1$ 인 경우 두 번째 줄부터 치노의 입력이 주어진다. 치노의 입력의 첫 번째 줄에는 트리의 정점 개수를 나타내는 정수 $N$ ( $100\le N\le1\\,000$ )이 주어진다. 그다음 줄부터 $N-1$ 개의 줄에 트리의 간선이 연결하는 두 정점을 나타내는 정수 $u$ 와 $v$ ( $1 \le u, v \le N$ , $u \ne v$ )가 각각 주어진다.

$T=2$ 인 경우 두 번째 줄부터 코코아의 입력이 주어진다. 코코아의 입력의 첫 번째 줄에는 정수 $N$ 과 $K$ ( $100\le N\le1\\,000$ )가 주어진다. $N$ 은 치노가 받은 트리의 정점 개수이고, $K$ 는 치노가 추가한 간선의 개수이다. 그다음 줄부터 $N+K-1$ 개의 줄에 그래프의 간선이 연결하는 두 정점을 나타내는 정수 $u$ 와 $v$ ( $1 \le u < v \le N$ )가 각각 주어진다. 각 간선은 $u < v$ 를 만족하도록 연결하는 두 정점의 순서가 조정되어 주어진다. 간선 사이의 순서는 $u$ 에 대해 오름차순으로, 만약 $u$ 가 같다면 $v$ 에 대해 오름차순으로 주어진다.

출력

치노의 입력 ( $T=1$ )에서, 치노는 첫 번째 줄에 하나의 정수 $K$ 를 출력해야 한다. 이 값은 $\left\lfloor \frac{N^2}{5} \right\rfloor$ 이상이어야 한다. 두 번째 줄부터 $K$ 개의 줄에 치노가 추가할 간선이 연결하는 두 정점을 나타내는 정수 $u$ 와 $v$ ( $1 \le u, v \le N$ , $u \ne v$ )를 각각 출력해야 한다. 출력하는 간선은 치노가 처음에 받은 트리에 존재하지 않는 간선이어야 하며, 중복되지 않아야 한다.

코코아의 입력 ( $T=2$ )에서, 코코아는 첫 번째 줄부터 $N-1$ 개의 줄에 치노에게 주어진 트리의 간선들이 연결하는 두 정점의 번호 $u$ 와 $v$ ( $1 \le u, v \le N$ , $u \ne v$ )를 각각 출력해야 한다. 출력하는 간선들은 중복되어서는 안 되며, 원래 트리에 간선 $(u,v)$ 가 있었다면 출력에 $(u,v)$ 혹은 $(v,u)$ 가 존재해야 한다.