마법사 루루와 마법의 숲

문제

이 문제는 투 스텝 문제이다.

성재와 오필은 마법사 루루의 음모에 빠져들어 성에 갇히게 되었다!

"너희들의 팀워크를 시험해 보도록 하지."

루루는 $1$번부터 $N$번까지 번호가 붙어 있는 $N$개의 정점과 $M$개의 트리로 이루어진 숲(forest) 하나를 갖고 있다. 이 숲을 '숲 $F$'라고 하자. 숲은 $1$개 이상의 연결 요소로 이루어져 있으며, 각각의 연결 요소가 트리(tree)인 그래프이다.

루루의 숲 $F$는 다음과 같은 성질을 가지고 있다.

숲 $F$를 이루는 각 트리는 $1$개 이상의 간선을 가진다.
숲 $F$를 이루는 각 트리의 간선 중 정확히 하나는 특별한 간선이다.

루루는 이 숲 $F$를 이용하여 성재와 오필에게 과제를 하나 내주고, 이들이 과제를 해결한다면 풀어주기로 약속했다. 루루는 성재와 오필이 서로 소통할 수 없도록 독방에 가두어 놓고, 다음과 같은 과정을 거치게 한다.

루루는 자신이 가진 숲 $F$를 두 개로 복제하여, 복제본 하나는 성재에게 주고, 나머지 하나는 자신이 가진다.
성재는 루루에게 받은 숲 $F$를 참고하여 $1$번부터 $N+1$번까지 번호가 붙은 $N+1$개의 정점을 가진 트리 $T$를 구성하여 루루에게 준다.
루루는 길이 $N+1$의 순열 $A = [A_1, \cdots, A_N, A_{N+1}]$를 정한다. 이때, $A_{N+1} = N+1$을 만족한다.
루루는 자신이 가진 숲 $F$와 성재가 만든 트리 $T$의 정점 번호를 순열 $A$를 이용하여 바꿔 새로운 숲 $F'$과 새로운 트리 $T'$를 만든다. 구체적으로는, 숲 $F$에서 $i$번 정점과 $j$번 정점을 연결하는 간선이 존재한다면, 숲 $F'$에 $A_i$번 정점과 $A_j$번 정점을 연결하는 간선을 추가한다. 만약 숲 $F$에서 $i$번 정점과 $j$번 정점을 연결하는 간선이 특별한 간선이라면, 숲 $F'$에서 $A_i$번 정점과 $A_j$번 정점을 연결하는 간선 역시 특별한 간선이 된다. 같은 방법으로 트리 $T$를 이용하여 트리 $T'$를 만든다.
루루는 트리 $T'$를 오필에게 준다. 오필은 트리 $T'$를 보고 루루가 가지고 있는 숲 $F'$를 알아맞혀야 한다. 구체적으로는, 오필은 $1$번부터 $N$번까지 번호가 붙어 있는 $N$개의 정점과 $M$개의 트리로 이루어져 있으며, 숲을 이루는 각 트리에서 정확히 하나의 간선이 특별한 간선인 숲을 만든다.

오필이 만든 숲이 루루가 가지고 있는 숲 $F'$과 일치한다면, 성재와 오필은 루루의 과제를 해결한 것이다. 만약 그렇지 않다면, 둘은 루루의 과제를 해내지 못한 것이다. 루루가 숲 $F$와 순열 $A$를 어떻게 선택하더라도 주어진 과제를 항상 해결할 수 있다.

만약 성재와 오필이 이 과제를 해내지 못한다면 둘은 영원히 루루의 성에 갇히게 될 것이다! 과연 성재와 오필은 루루의 성에서 탈출할 수 있을까? 당신이 성재와 오필을 도와주도록 하자!

입력

당신의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스코드에 두 가지 실행 과정을 모두 구현해야 한다.

첫째 줄에 실행의 번호를 나타내는 정수 $R$이 주어진다. $(1 \leq R \leq 2)$

$R=1$일 때 당신은 성재의 역할을 맡아서, 숲 $F$를 받아서 트리 $T$를 출력해야 한다.

둘째 줄에 숲 $F$의 정점의 개수를 의미하는 정수 $N$과, 숲에 존재하는 트리의 개수를 의미하는 정수 $M$이 공백으로 구분되어 주어진다. $(2 \leq N \leq 5\,000;$ $1 \leq M \leq \lfloor \frac{N}{2} \rfloor)$

셋째 줄부터 $N-M$개의 줄에 걸쳐 정수 $u$와 $v$가 공백으로 구분되어 주어진다. 이는 숲 $F$에서 $u$번 정점과 $v$번 정점이 간선으로 연결되어 있다는 것을 의미한다. $(1 \leq u, v \leq N;$ $u \neq v)$

이후 $M$개의 줄에 걸쳐 정수 $u$와 $v$가 공백으로 구분되어 주어진다. 이는 숲 $F$에서 $u$번 정점과 $v$번 정점을 연결하는 간선이 특별한 간선이라는 것을 의미한다.

주어지는 모든 특별한 간선 u v는 앞서 등장한 간선 목록에 반드시 포함되어 있음이 보장된다. 숲을 구성하는 각 트리당 정확히 하나의 특별한 간선이 존재함이 보장된다. $(1 \leq u, v \leq N;$ $u \neq v)$

$R=2$일 때 당신은 오필의 역할을 맡아서, 트리 $T'$를 받아서 숲 $F'$를 출력해야 한다.

둘째 줄에 숲 $F$과 숲 $F'$의 정점의 개수를 의미하는 정수 $N$이 주어진다. 두 번째 시행에서는 $M$이 주어지지 않는다.

셋째 줄부터 $N$개의 줄에 걸쳐 정수 $u$와 $v$가 공백으로 구분되어 주어진다. 이는 트리 $T'$에서 $u$번 정점과 $v$번 정점이 간선으로 연결되어 있다는 것을 의미한다. $(1 \leq u, v \leq N + 1;$ $u \neq v)$

출력

$R=1$일 때, $N$개의 줄에 걸쳐 각 줄마다 트리 $T$의 간선이 연결하는 두 정점의 번호 $u$와 $v$를 출력한다. $(1 \le u, v \le N + 1;$ $u \neq v)$

$R=2$일 때, 첫째 줄에 $M$의 값을 출력한다.

둘째 줄부터 $N-M$개의 줄에 걸쳐 각 줄마다 숲 $F'$의 간선이 연결하는 두 정점의 번호 $u$와 $v$를 출력한다. $(1 \le u, v \le N;$ $u \neq v)$

이후 $M$개의 줄에 걸쳐 각 줄마다 숲 $F'$의 특별한 간선이 연결하는 두 정점의 번호 $u$와 $v$를 출력한다. $(1 \le u, v \le N;$ $u \neq v)$

출력 형식을 지키지 않거나, 프로그램이 정상적으로 종료되지 않는 경우, 예상치 못한 채점 결과를 받을 수 있다.

힌트

길이 $K$의 순열은 $1$부터 $K$까지의 수가 정확히 한 번 등장하는 수열을 말한다. 예를 들어, $[3,5,1,2,4]$와 $[1,3,2]$는 순열이지만, $[2,3,2]$또는 $[0]$은 순열이 아니다.
채점 프로그램은 간선의 출력 순서를 고려하지 않는다. 또한 간선 u v와 v u를 동일한 간선으로 판단한다. 즉, $2$번째 실행의 입력으로 주어지는 트리 $T'$의 간선 순서 및 각 간선에서 등장하는 정점 번호의 순서는 트리 $T$와 무관하다. 또한, $2$번째 실행에서 출력하는 간선의 순서와 특별한 간선의 순서, 그리고 각 간선에서 등장하는 정점 번호의 순서를 고려하지 않고 결과를 채점한다.