학생 커플
| 실행 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 128 MB |
📃 해결할 문제
원구와 수진은 학교에서 유명한 학생 커플입니다. 학교의 수업 일정이 매일 바뀌기 때문에, 두 사람은 그 때마다 멀리 떨어져 볼 수 없습니다.
학교의 교실과 복도는 '트리' 구조를 이룹니다. 각 교실은 다른 교실과 정확히 정확히 하나의 고유한 길이 있고, 각 교실(루트인 교실 #1번 제외)은 하나의 부모 노드를 가지고 있습니다.
원구와 수진은 원구의 교실과 수진의 교실의 부모가 되는 가장 가까운 교실에서 항상 만나기로 결정했습니다.
학교에는 N (1<=N<=1,000) 개의 교실 (1..N까지 번호가 매겨짐)에 대한 지도가 존재하고, 이 지도는 교실 1을 제외한 각 교실의 부모 P_i (1<=P_i<=N)를 알려줍니다.
다음 M(1 <= M <= 1,000)일 동안의 수업 일정도 홈페이지에 공지되었으므로, 원구와 수진은 데이트를 하기위해 어디에서 만날지만 결정하면 됩니다. k일째에 원구는 교실 B_k (1<=B_k <=N) 교실에 있고, 수진은 J_k (1<=J_k<=N) 교실에 있습니다.
주어진 지도와 일정을 가지고, 원구와 수진이 만날 장소를 찾아주세요.
예를 들어, 다음 학교 지도가 있다고 가정하면:
교실 부모 교실
[1] --------- ----------------
/ | \ 1 ---
/ | \ 2 1
[2] [3] [6] 3 1
/ | \ 4 2
/ | \ 5 8
[4] [8] [9] 6 1
/ \ 7 8
/ \ 8 6
[5] [7] 9 6원구와 수진이 선택한 만나는 교실은 초기 위치에 따라 6일 동안의 수업 일정이 주어졌을 때 다음과 같습니다.
원구 수진 만나는 교실
-------- -------- ---------------
2 7 1
4 2 2
1 1 1
4 1 1
7 5 8
9 5 6💻 입력
- 첫 번째 줄 : 두 개의 공백으로 구분된 정수: N과 M
- 두 번째 줄부터 N번째 줄 : i 번째 줄에는 교실 i의 부모를 설명하는 단일 정수: P_i
- N + 1번째 줄부터 N + M번째 줄 : k + N줄은 원구와 수진의 각각의 교실을 두 개의 공백으로 구분하여 설명합니다: B_k와 J_k
🖨️ 출력
- 첫 번째 줄부터 M 번째 줄: j 번째 줄에는 입력의 j + N 줄에 대해 원구와 수진이 만나는 교실이 포함됩니다
💻 예제 입력 1
9 6 1 1 2 8 1 8 6 6 2 7 4 2 3 3 4 1 7 5 9 5
🖨️ 예제 출력 1
1 2 3 1 8 6