27456번 - 치노와 코코아 투 스텝

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

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

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

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

첫 번째 줄에는 입력의 종류를 나타내는 정수 $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)$가 존재해야 한다.