시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB35161356.522%

문제

이 문제는 한 번 채점할 때 참가자의 프로그램을 $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)$가 존재해야 한다.

예제 입력 1

1
6
2 6
1 2
3 1
5 2
2 4

예제 출력 1

2
2 3
6 1

문제의 이해를 돕기 위한 $N=6$의 예시로, $N$과 $K$의 범위가 문제의 조건을 만족하지 않기 때문에 채점에는 사용되지 않는다. 먼저 치노의 입력에서 치노에게 주어진 정점 $6$개의 트리에 치노가 $1$, $6$번 정점을 잇는 간선과 $2$, $3$번 정점을 잇는 간선을 추가하는 것을 보여준다.

예제 입력 2

2
6 2
1 2
1 3
1 6
2 3
2 4
2 5
2 6

예제 출력 2

2 1
4 2
2 5
2 6
1 3

이어서 예제 입력 1에서 치노에게 주어졌던 $N=6$의 트리에 치노가 추가한 $K=2$ 개의 간선이 더해진 그래프가 코코아의 입력으로 주어진다. 입력 형식에 설명한 것과 같이 간선의 순서와 그리고 각각의 간선이 연결하는 두 정점의 순서가 조정된 것을 알 수 있다.

코코아는 주어진 그래프의 간선 중 처음에 치노에게 주어진 트리에 속하는 $5$개의 간선을 출력하였다.

출처

Contest > BOJ User Contest > 아니메컵 > 아니메컵 2쿨 L번

채점 및 기타 정보

  • 예제는 채점하지 않는다.