24027번 - 두 트리 스페셜 저지

정점의 개수가 $N$으로 같은 빨간색 트리와 파란색 트리가 주어진다. 각 트리의 각 정점은 1번브터 $N$번까지의 번호가 부여되어 있다. 이제 파란색 트리의 정점들을 빨간색 트리의 정점들과 일대일 대응시켜 파란 트리를 빨간 트리 위에 올려두어. 각각 대응된 정점끼리 합쳐진 새로운 그래프를 하나 만들고자 한다. 이때 합쳐진 그래프에서는 중복 간선이 없어야 한다. 즉, 어떤 두 정점에 대해서도 그 정점들 사이를 직접적으로 연결하는 간선이 0개 혹은 1개 있어야 한다.

위 조건을 만족하는 일대일 대응을 구해라. 만약 가능한 경우가 여러 개 있다면 어떤 방법을 선택해도 좋다.

첫째 줄에 각 트리의 정점의 개수 $N$이 주어진다. ($2 \leq N \leq 200,000$)

이후 $N-1$줄에 걸쳐 빨간색 트리의 간선에 대한 정보가 주어진다. 그 이후 $N-1$줄에 걸쳐 파란색 트리의 간선에 대한 정보가 주어진다.

$N$개의 수를 한 줄에 공백으로 구분하여 출력한다. 이때, $i$번째 수는 파란색 트리의 $i$번 정점이 일대일 대응을 통해 합쳐진 빨간색 트리의 정점 번호이다. 만약 조건을 만족하는 일대일 대응이 존재하지 않는다면 대신 -1을 출력한다.