Tổ tiên chung thấp nhất (LCA)

Một công ty có $n$ nhân viên, đánh số từ $1$ đến $n$. Nhân viên số $1$ là tổng giám đốc. Mỗi nhân viên từ $2$ đến $n$ có đúng một người quản lý trực tiếp $e_i$ (với $e_i<i$).

Trả lời $q$ truy vấn: với mỗi truy vấn $(a,b)$, hãy tìm người quản lý chung thấp nhất (LCA) của hai nhân viên $a$ và $b$ — tức là người quản lý chung ở cấp cao nhất trong hệ thống mà vẫn là cấp trên của cả hai.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$.

Dòng thứ hai chứa $n-1$ số nguyên $e_2,e_3,\dots ,e_n$: người quản lý trực tiếp của mỗi nhân viên.

• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$.

Dữ liệu ra

Với mỗi truy vấn, in ra người quản lý chung thấp nhất của $a$ và $b$.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le e_i\le i-1$
• $1\le a,b\le n$

Ví dụ