메뉴 건너뛰기

문제

18nh4 족보   0  

시간메모리제출 올바른 답 비율
2초512MB
0
0
0.0%


나의 횟수나의 최근 판정시도 성공 비율
00
0.0%
족보 

김 박사는 고대 아마존 왕국 유적지를 탐험하다가 여왕 족보 두 개를 발견하 였다. 각 족보에는 최초의 여왕 1명과그 여왕의 여자 후손들 간의 부모-자식 관계가 아래와 같이 나무 형태로 기록 되어 있다. 예를 들면, <그림1>에서 C는 최초의 여왕이며 F와 D는 C의 자식이 다. 한 사람의 자식들 사이에는 순서를 구별하지 않는다.

<그림1>

두 족보가 발견되었을 때 다음과 같이 정의되는 단위훼손이 0번 이상 발생했다는 것을 알았다.

* 단위훼손: 부모 P와 P의 자식 Q가 한사람으로 합쳐진다. 두 사람의 모든 자식들(Q 제외)은 합쳐진 한 사람의 자식이 된다.

예를 들면, 다음 <그림 2>에서 A와 F가 합쳐지는 단위훼손이 일어나면 <그림 3>과 같이 변화된다. 또한, <그림 3>에서 추가적으로 B와 D가 합쳐지는 단위훼손 <그림 4>이 일어나면 <그림 5>와 같이 변화된다.

<그림2>
<그림3>
<그림4>
<그림5>

<그림 5>에서 E와 G가 합쳐지는 단위훼손<그림 6>이 일어나면 <그림 7>과 같이 된다.

<그림6>
<그림7>

다행히도 족보에서 자식이 없는 사람 (그림에서 숫자 이름에 해당)이 포함된 단위훼손은 발생하지 않았다. 또한, 자식이 없는 사람들은 모두 이름이 족보에 적혀있었고 이름은 서로 다르다. 하지만 자식이 있는 사람들(그림에서 알파벳 이름에 해당)은 이름이 하나도 남아 있지 않다. 따라서 발견된 족보의 형태는 <그림 8>과 같다.

<그림8>

동일한 원본에서 단위 훼손이 일어나는 방법에 따라 여러 가지 결과가 나올 수 있다는 것을 짐작할 수 있다. 하지만, <그림 9>의 두 족보는 동일한 원본에서 만들 수 없는 예이다.

<그림9>

입력으로 주어진 두 족보가 같은 원본 에서 0번 이상의 단위훼손을 통해 만들어질 수 있는지를 판단하는 프로그램을 작성하라. 입력으로 주어진 두 족보 S와 T에서 자식이 없는 사람들의 이름의 집합이 동일하다. 즉, 족보 S에서 자식이 없는 사람들의 이름으로 집합을 만들고 족보 T에서 자식이 없는 사람들의 이름으로 집합을 만들면 두 집합은 동일하다.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 첫 번째 족보의 사람 수 N1, 두 번째 족보의 사람 수 N2, 각 족보에서 자식이 없는 사람들의 수 K가 주어진다. 첫 번째 족보의 사람 들은 1부터 N1까지 번호가 붙어 있고 두 번째 족보의 사람들은 1부터 N2까지 번호가 붙어 있다. 두 족보 모두, 1번부터 K번까지의 사람들은 자식이 없다. 또한, 1번부터 K번까지의 사람들은 각각 같은 번호인 사람끼리 이름이 같다.

다음 줄에는 첫 번째 족보에서 각 사람의 부모의 번호가 사람의 번호 순서대로 주어진다. 부모가 없는 경우는 0이 주어진다. 다음 줄에는 두 번째 족보에서 각 사람의 부모의 번호가 사람의 번호 순서대로 주어진다. 부모가 없는 경우는 0이 주어진다.

 

< 부분문제의 제약 조건 >

모든 부분 문제에서 1 ≤ K < N1N2 이다.

  • 부분문제 1 (17점) : 2 ≤ N1N2 ≤ 300이고 첫 번째 족보에는 단위훼손이 없다.
  • 부분문제 2 (27점) : 2 ≤ N1N2 ≤ 300이다.
  • 부분문제 3 (15점) : 2 ≤ N1N2 ≤ 5,000이다.
  • 부분문제 3 (41점) : 2 ≤ N1N2 ≤ 300,000이다.
 
출력

표준 출력으로, 두 족보가 같은 원본에서 만들어질 수 있는 것들인 경우 YES를, 그것이 불가능한 경우 NO를 영어 대문자로 출력한다.

예시
1입력
3 3 2
3 3 0
3 3 0
출력
YES
2입력
5 5 3
4 4 5 5 0
4 5 5 0 4
출력
NO
3입력
7 8 4
7 7 6 6 0 5 5
6 7 7 8 0 5 5 5
출력
NO
출처
2018년 한국정보올림피아드 전국 본선 고등부 4번
위로