3237 : 족보
- 제한시간
- 2000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 6 회
- 시도횟수
- 13 회
문제
김 박사는 고대 아마존 왕국 유적지를 탐험하다가 여왕 족보 두 개를 발견하였다.
각 족보에는 최초의 여왕 1명과 그 여왕의 여자 후손들 간의 부모-자식관계가 아래와 같이 나무 형태로 기록되어 있다.
예를 들면, 그림 1에서 C는 최초의 여왕이며 F와 D는 C의 자식이다.
한 사람의 자식들 사이에는 순서를 구별하지 않는다.
단위훼손: 부모 P와 P의 자식 Q가 한 사람으로 합쳐진다.
두 사람의 모든 자식들(Q 제외)은 합쳐진 한 사람의 자식이 된다.
예를 들면, 다음 그림 2에서 A와 F가 합쳐지는 단위훼손이 일어나면 그림 3과 같이 변화된다.
또한, 그림 3에서 추가적으로 B와 D가 합쳐지는 단위훼손 (그림 4)이 일어나면 그림 5와 같이 변화된다.
그림 5에서 E와 G가 합쳐지는 단위훼손(그림 6)이 일어나면 그림 7과 같이 된다.
동일한 원본에서 단위 훼손이 일어나는 방법에 따라 여러 가지 결과가 나올 수 있다는 것을 짐작할 수 있다.
하지만, 그림 9의 두 족보는 동일한 원본에서 만들 수 없는 예이다.
입력형식
표준 입력으로 다음 정보가 주어진다.
첫 번째 줄에는 첫 번째 족보의 사람 수 N1, 두 번째 족보의 사람 수 N2, 각 족보에서 자식이 없는 사람들의 수 K가 주어진다.
첫 번째 족보의 사람들은 1부터 N1까지 번호가 붙어 있고
두 번째 족보의 사람들은 1부터 N2까지 번호가 붙어 있다.
두 족보 모두, 1번부터 K번까지의 사람들은 자식이 없다.
또한, 1번부터 K번까지의 사람들은 각각 같은 번호인 사람끼리 이름이 같다.
다음 줄에는 첫 번째 족보에서 각 사람의 부모의 번호가 사람의 번호 순서대로 주어진다. 부모가 없는 경우는 0이 주어진다.
다음 줄에는 두 번째 족보에서 각 사람의 부모의 번호가 사람의 번호 순서대로 주어진다. 부모가 없는 경우는 0이 주어진다.
출력형식
표준 출력으로, 두 족보가 같은 원본에서 만들어 질 수 있는 것들인 경우 YES를, 그것이 불가능한 경우 NO를 영어 대문자로 출력한다.
[부분문제의 제약 조건]
모든 부분문제에서 1 ≤ K < N1, N2 이다.
* 부분문제 1: 전체 점수 100점 중 17점에 해당하며 2 ≤ N1, N2 ≤ 300 이고 첫 번째 족보에는 단위훼손이 없다.
* 부분문제 2: 전체 점수 100점 중 27점에 해당하며 2 ≤ N1, N2 ≤ 300 이다.
* 부분문제 3: 전체 점수 100점 중 15점에 해당하며 2 ≤ N1, N2 ≤ 5,000 이다.
* 부분문제 4: 전체 점수 100점 중 41점에 해당하며 2 ≤ N1, N2 ≤ 300,000 이다.
입력 예3 3 2 3 3 0 3 3 0 |
출력 예YES |
입력 예5 5 3 4 4 5 5 0 4 5 5 0 4 |
출력 예NO |
입력 예7 8 4 7 7 6 6 0 5 5 6 7 7 8 0 5 5 5 |
출력 예NO |