30832번 - 트리 재구성하기 스페셜 저지

문제

정점의 개수가 $N$인 두 트리 $A,ドル $B$가 주어진다. 다음의 시행을 2ドルN$번 이하로 하여 $A$를 $B$와 똑같이 만들어 보자.

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

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

입력

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

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

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

출력

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

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

제한

힌트

두 트리 $A$와 $B$가 같다는 것은 $A$의 $a$번 정점과 $b$번 정점을 연결하는 간선이 존재할 때, $B$에도 $a$번 정점과 $b$번 정점을 연결하는 간선이 존재함을 의미한다.