P3019 [USACO11MAR] Meeting Place S

贝西和乔内尔是好朋友。由于农夫约翰每天都会重新安排奶牛的放牧地点，有时他们相距甚远，无法交谈。 农夫约翰的农场上的牧场和路径形成了一种「树」结构。每个牧场到其他任何牧场都有且仅有一条独特的路径，并且每个牧场（除了牧场 #1，即「根」）都有一个父节点。 贝西和乔内尔决定，他们总是会在一个既是乔内尔牧场的祖先又是贝西牧场的祖先的最近的牧场见面。 农夫约翰创建了一张他的 $N (1 \le N \le 1,000)$ 个牧场（编号为 $1$ 到 $N$）的地图，地图上标明了每个牧场的父节点 $P_i (1 \le P_i \le N)$，除了牧场 $1$，它没有父节点。 农夫约翰发布了他未来 $M (1 \le M \le 1,000)$ 天的放牧计划，因此贝西和乔内尔正在决定他们每天应该在哪里见面进行闲聊。在第 $k$ 天，贝西在牧场 $B_k (1 \le B_k \le N)$，乔内尔在牧场 $J_k (1 \le J_k \le N)$。 给定地图和计划，帮助贝西和乔内尔找到他们的会面地点。 例如，考虑以下农场布局： ```plain 牧场 父牧场 [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 ``` 以下是贝西和乔内尔在给定六天的初始放牧地点计划时选择的会面地点： ```plain 贝西 乔内尔 会面地点 -------- -------- --------------- 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$

* 第 $1$ 行到第 $M$ 行：第 $j$ 行包含贝西和乔内尔在输入的第 $j+N$ 行使用的会面地点

（由 ChatGPT 4o 翻译）