Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một cây gồm $N$ đỉnh gốc tại $1$. Với mỗi truy vấn gồm đỉnh $u$ và số nguyên $K$, hãy tìm tổ tiên thứ $K$ của $u$ (tổ tiên thứ $0$ là chính $u$, tổ tiên thứ $1$ là cha của $u$, ...). Nếu không tồn tại, in ra -1.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, Q$. $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh của cây. $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, K$.

Dữ liệu ra

Gồm $Q$ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.

Ví dụ
Input Output
5 4
1 2
1 3
2 4
2 5
4 1
4 2
4 3
5 0
2
1
-1
5
Giới hạn

$1 \le N, Q \le 10^5$, $0 \le K \le N$.

Draft saved