문제
정점의 개수가 N으로 같은 빨간색 트리와 파란색 트리가 주어진다. 각 트리의 각 정점은 1번브터 N번까지의 번호가 부여되어 있다.
이제 파란색 트리의 정점들을 빨간색 트리의 정점들과 일대일 대응시켜 파란 트리를 빨간 트리 위에 올려두어. 각각 대응된 정점끼리 합쳐진 새로운 그래프를 하나 만들고자 한다. 이때 합쳐진 그래프에서는 중복 간선이 없어야 한다. 즉, 어떤 두 정점에 대해서도 그 정점들 사이를 직접적으로 연결하는 간선이 0개 혹은 1개 있어야 한다.
위 조건을 만족하는 일대일 대응을 구해라. 만약 가능한 경우가 여러 개 있다면 어떤 방법을 선택해도 좋다.
입력
첫째 줄에 각 트리의 정점의 개수 N (2 <= N <= 200,000)이 주어진다.
이후 N-1줄에 걸쳐 빨간색 트리의 간선에 대한 정보가 주어진다.
그 이후 N-1줄에 걸쳐 파란색 트리의 간선에 대한 정보가 주어진다.
출력
N개의 수를 한 줄에 공백으로 구분하여 출력한다. 이때, i번째 수는 파란색 트리의 i번 정점이 일대일 대응을 통해 합쳐진 빨간색 트리의 정점 번호이다. 만약 조건을 만족하는 일대일 대응이 존재하지 않는다면 대신 -1을 출력한다.
예제
10
9 4
9 10
9 2
9 8
9 3
9 6
2 7
9 1
2 5
8 1
2 6
5 8
10 4
8 2
5 3
8 7
7 9
5 10
10 2 7 1 3 4 5 6 9 8
출처
mhy908
로그인해야 코드를 작성할 수 있어요.