Đỉnh thứ k trên đường đi

Cho một cây gồm $n$ đỉnh đánh số từ $1$ đến $n$. Các cạnh được cho theo thứ tự và chiều bất kỳ.

Với hai đỉnh $u$ và $v$, đường đi từ $u$ tới $v$ là dãy các đỉnh $x_0=u,x_1,\dots ,x_L=v$ trong đó hai đỉnh liên tiếp được nối bởi một cạnh và không đỉnh nào lặp lại; $L$ là số cạnh của đường đi.

Hãy trả lời $q$ truy vấn, mỗi truy vấn cho $u,v,k$ và hỏi đỉnh $x_k$ trên đường đi từ $u$ tới $v$. Nếu $k>L$ thì in ra $-1$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $q$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$ cho biết có cạnh nối đỉnh $u$ và đỉnh $v$.
• $q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u,v,k$ là một truy vấn.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ là đáp án của truy vấn thứ $i$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le q\le {10}^5$
• $1\le u,v\le n$; với các cạnh thì $u\ne v$, với truy vấn thì $u$ có thể bằng $v$.
• $0\le k\le n$

Ví dụ