베시와 조넬은 절친한 친구이다. 농부 존이 소들의 풀이 있는 장소를 뒤죽박죽으로 만든 이후로, 그들은 가끔 서로 꽤 멀리 떨어져 있어 떠들지 못한다.

농부 존의 농장에서 초원들과 길들은 트리 구조 형태로 되어 있다.

각 초원은 아무 다른 초원과 정확히 하나의 길만을 가지고 있고, 또 하나의 부모 노드를 가지고 있다. (단, 루트 노드인 #1 제외) 베시와 조넬은 그들은 조넬의 초원과 베시의 초원에서 가장 가까운 조상 노드에 속한 초원에서 만나기로 결정했다.

농부 존은 N (1≤N≤1,000)개의 초원 (초원은 1..N의 순서로 나열됨)들과 그들의 조상 노드를 의미하는 P_i (1≤P_i≤N, 루트 노드인 #1 제외)를 나타내는 지도를 만들었다.

농부 존은 앞으로 M(1≤M≤1,000)일 동안의 그의 방목 스케줄을 공개하였다. 그래서 베시와 조넬은 그들이 매일 언제 만날지를 정하고 있다. k번째 날에는, 베시는 초원B_k(1≤B_k≤N)에, 조넬은 초원 J_k(1≤J_k≤N)에 있다.

농부 존의 지도와 방목 스케줄이 주어질 때, 베시와 조넬이 만날 장소를 정하는 것을 도와 주자.

예로 들어, 아래와 같은 지도가 주어졌다고 하자:

                            Pasture      Parent Pasture
             [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

              Bessie      Jonell       Meeting Place
             --------    --------     ---------------
                 2           7               1
                 4           2               2
                 1           1               1
                 4           1               1
                 7           5               8
                 9           5               6

입력

• 줄 1: 공백으로 구분된 N과 M이 주어진다.
• 줄 2~N: 줄 i에 i의 부모 노드, 즉 P_i가 주어진다.
• 줄 N+1..N+M: 줄 k+N에 B_k와 J_k가 공백으로 구분되어 주어진다.

출력

입출력 예

입력

9 6
1
1
2
8
1
8
6
6
2 7
4 2
3 3
4 1
7 5
9 5

출력

1
2
3
1
8
6

출처:usaco 2011 MAR silver
번역:tncks0121