트리 재구성하기

시간 제한1초메모리 제한1024 MB

요약

두 트리 A와 B가 주어질 때, 간선의 한쪽 끝을 옮기는 연산으로 A를 B와 같게 만드는 2N 이하의 연산 순서를 구합니다.

문제

정점이 $N$ 개인 두 트리 $A$ , $B$ 가 주어진다. 다음 시행을 $2N$ 번 이하로 반복해서 $A$ 를 $B$ 와 똑같이 만들어 보자.

$A$ 의 서로 다른 세 정점 $a$ , $b$ , $c$ 를 고른다. $a$ 와 $b$ , $b$ 와 $c$ 는 각각 간선으로 연결되어 있어야 한다.
$a$ 와 $b$ 사이의 간선을 제거하고 $a$ 와 $c$ 사이에 간선을 추가한다.

$2N$ 번 이하의 시행으로 $A$ 와 $B$ 를 똑같이 만드는 것이 항상 가능함을 증명할 수 있다. 시행의 횟수를 최소화할 필요는 없다.

첫 번째 줄에 트리의 정점 개수 $N$ 이 주어진다. $(4 \leq N \leq 1\ 000)$

다음 $N-1$ 개의 줄에 트리 $A$ 의 두 정점 $u_i$ , $v_i$ 가 공백으로 구분되어 주어진다. 두 정점은 간선으로 연결되어 있다. $(1 \leq u_i, v_i \leq N; u_i \neq v_i)$

다음 $N-1$ 개의 줄에 트리 $B$ 의 두 정점 $u_i$ , $v_i$ 가 공백으로 구분되어 주어진다. 두 정점은 간선으로 연결되어 있다. $(1 \leq u_i, v_i \leq N; u_i \neq v_i)$

첫 번째 줄에 시행 횟수 $k$ 를 출력한다. $k$ 는 $2N$ 이하인 음이 아닌 정수여야 한다.

다음 $k$ 개의 줄에 각 시행에서 고른 $A$ 의 정점 $a$ , $b$ , $c$ 를 공백으로 구분하여 출력한다. 각 시행을 순서대로 출력해야 한다.

두 트리 $A$ 와 $B$ 가 같다는 것은, $A$ 에서 정점 $x$ 와 $y$ 를 잇는 간선이 존재할 때 $B$ 에도 정점 $x$ 와 $y$ 를 잇는 간선이 존재함을 뜻한다.