트리 동형

미술 시간 과제는 번호가 매겨진 트리를 그리는 것이었다. 번호가 매겨진 트리를 그리려면 먼저 종이에 $0 \ldots N-1$의 정수를 적고, 그다음 일부 정수 쌍 사이에 $N-1$개의 선을 그어 연결한다. 선은 어떤 정수에서 출발하든 선을 따라 다른 모든 정수에 도달할 수 있도록 그어야 한다.

두 학생이 정수 개수가 같은 트리를 그렸다. 선생님은 표절을 의심했다. 한 학생이 다른 학생의 트리를 베끼고 정수 일부만 바꾸고 선은 그대로 두었다고 생각한다.

$N$개의 정수로 이루어진 두 트리가 주어졌을 때, 첫 번째 트리의 정수 일부를 바꿔서 두 번째 트리로 만들 수 있는지 판단하는 프로그램을 작성하라. 아무것도 바꾸지 않거나 모두 바꾸는 경우도 포함한다. 가능하다면 그 변경 내용도 출력해야 한다.

첫 줄에 각 트리의 정수 개수 $N$이 주어진다 ($1 \le N \le 100\,000$). 이어지는 $N-1$개 줄에는 두 정수 $s$와 $t$가 주어지며, 첫 번째 트리에서 정수 $s$와 $t$ 사이에 선이 있다는 뜻이다 ($0 \le s < t < N$). 그다음 $N-1$개 줄에는 두 정수 $u$와 $v$가 주어지며, 두 번째 트리에서 정수 $u$와 $v$ 사이에 선이 있다는 뜻이다 ($0 \le u < v < N$).

첫 번째 트리를 두 번째 트리로 바꿀 수 없으면 첫 줄에 EI를 출력한다. 바꿀 수 있으면 첫 줄에 JAH를 출력하고, 이어지는 $N$개 줄에 정수 $p_i$를 각각 출력한다. $p_i$는 첫 번째 트리의 정수 $i$를 $p_i$로 바꿔야 한다는 뜻이다.