📖 Bài giảng & lời giải: đây là Bài tập 1 trong bài giảng Bài 34: LCA, nhảy nhị phân trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Công ty có $n$ nhân viên đánh số từ $1$ tới $n$, nhân viên $1$ là giám đốc. Với mỗi $i \ge 2$, sếp trực tiếp của nhân viên $i$ là nhân viên $p_i$; đảm bảo quan hệ sếp – nhân viên tạo thành một cây có gốc là nhân viên $1$ (chú ý: $p_i$ không nhất thiết nhỏ hơn $i$).

Có $q$ câu hỏi, mỗi câu cho hai số $u$ và $k$: bắt đầu từ nhân viên $u$, đi lên $k$ cấp (mỗi cấp là chuyển từ một người lên sếp trực tiếp của người đó) thì gặp ai? Đi lên $0$ cấp thì gặp chính $u$. Nếu phía trên $u$ có ít hơn $k$ cấp thì in $-1$.

Dữ liệu vào

• Dòng 1: hai số nguyên $n, q$ ($1 \le n \le 10^5$, $1 \le q \le 10^5$).
• Dòng 2: $n - 1$ số nguyên $p_2, p_3, \ldots, p_n$ ($1 \le p_i \le n$). Khi $n = 1$ dòng này để trống.
• $q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u, k$ ($1 \le u \le n$, $0 \le k \le n$).

Kết quả

In $q$ dòng, dòng thứ $j$ là số hiệu nhân viên tìm được cho câu hỏi thứ $j$, hoặc $-1$ nếu không tồn tại.

Sample Input

12 4
1 1 2 2 3 4 4 5 6 7 11
12 5
12 3
9 4
10 0

Sample Output

1
4
-1
10

Note

Ở truy vấn đầu tiên, đi lên từ nhân viên $12$ lần lượt gặp $11, 7, 4, 2, 1$ nên lên $5$ cấp là gặp giám đốc $1$. Nhân viên $9$ chỉ có $3$ cấp phía trên ($5, 2, 1$) nên lên $4$ cấp là không tồn tại.