{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eTrong bài toán này, bạn sẽ phải giúp quân đội Berland tổ chức hệ thống giao tiếp lệnh của họ.\u003c/p\u003e\u003cp\u003eCó $$$n$$$ sĩ quan trong quân đội Berland. Sĩ quan đầu tiên là chỉ huy của quân đội, và anh ta không có bất kỳ cấp trên nào. Mỗi sĩ quan khác đều có đúng một cấp trên trực tiếp. Nếu sĩ quan $$$a$$$ là cấp trên trực tiếp của sĩ quan $$$b$$$, thì chúng ta cũng có thể nói rằng sĩ quan $$$b$$$ là cấp dưới trực tiếp của sĩ quan $$$a$$$.\u003c/p\u003e\u003cp\u003eSĩ quan $$$x$$$ được coi là cấp dưới (trực tiếp hoặc gián tiếp) của sĩ quan $$$y$$$ nếu một trong những điều kiện sau đây được thỏa mãn:\u003c/p\u003e\u003cul\u003e \u003cli\u003e sĩ quan $$$y$$$ là cấp trên trực tiếp của sĩ quan $$$x$$$; \u003c/li\u003e\u003cli\u003e cấp trên trực tiếp của sĩ quan $$$x$$$ là cấp dưới của sĩ quan $$$y$$$. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eVí dụ, trên hình dưới, các cấp dưới của sĩ quan $$$3$$$ là: $$$5, 6, 7, 8, 9$$$.\u003c/p\u003e\u003cp\u003eCấu trúc của quân đội Berland được tổ chức theo cách mà mỗi sĩ quan, ngoại trừ chỉ huy, đều là cấp dưới của chỉ huy của quân đội.\u003c/p\u003e\u003cp\u003eĐể cụ thể, hãy biểu diễn quân đội Berland như một cây gồm $$$n$$$ đỉnh, trong đó đỉnh $$$u$$$ tương ứng với sĩ quan $$$u$$$. Cha của đỉnh $$$u$$$ tương ứng với cấp trên trực tiếp của sĩ quan $$$u$$$. Gốc (có chỉ số $$$1$$$) tương ứng với chỉ huy của quân đội.\u003c/p\u003e\u003cp\u003eBộ Quốc phòng Chiến tranh Berland đã yêu cầu bạn trả lời $$$q$$$ truy vấn, truy vấn thứ $$$i$$$ được đưa ra dưới dạng $$$(u_i, k_i)$$$, trong đó $$$u_i$$$ là một sĩ quan nào đó, và $$$k_i$$$ là một số nguyên dương.\u003c/p\u003e\u003cp\u003eĐể xử lý truy vấn thứ $$$i$$$, hãy tưởng tượng cách một lệnh từ $$$u_i$$$ lan ra đến các cấp dưới của $$$u_i$$$. Thuật toán DFS (duyệt theo chiều sâu) điển hình được sử dụng ở đây.\u003c/p\u003e\u003cp\u003eGiả sử sĩ quan hiện tại là $$$a$$$ và anh ta lan truyền một lệnh. Sĩ quan $$$a$$$ chọn $$$b$$$ — một trong số các cấp dưới trực tiếp của mình (tức là một đứa trẻ trong cây) chưa nhận được lệnh này. Nếu có nhiều cấp dưới trực tiếp như vậy, thì $$$a$$$ chọn đứa có chỉ số nhỏ nhất. Sĩ quan $$$a$$$ ra lệnh cho sĩ quan $$$b$$$. Sau đó, $$$b$$$ sử dụng chính xác cùng thuật toán để lan truyền lệnh đến cây con của mình. Sau khi $$$b$$$ hoàn thành việc lan truyền lệnh, sĩ quan $$$a$$$ chọn cấp dưới trực tiếp tiếp theo (sử dụng chiến lược tương tự). Khi sĩ quan $$$a$$$ không thể chọn bất kỳ cấp dưới trực tiếp nào vẫn chưa nhận được lệnh này, sĩ quan $$$a$$$ kết thúc việc lan truyền lệnh.\u003c/p\u003e\u003cp\u003eHãy xem ví dụ sau:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/4c032195c19c77cbe8a2e19729e00cfa?v\u003d1716779644\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eNếu sĩ quan $$$1$$$ lan truyền một lệnh, các sĩ quan sẽ nhận lệnh theo thứ tự sau: $$$[1, 2, 3, 5 ,6, 8, 7, 9, 4]$$$.\u003c/p\u003e\u003cp\u003eNếu sĩ quan $$$3$$$ lan truyền một lệnh, các sĩ quan sẽ nhận lệnh theo thứ tự sau: $$$[3, 5, 6, 8, 7, 9]$$$.\u003c/p\u003e\u003cp\u003eNếu sĩ quan $$$7$$$ lan truyền một lệnh, các sĩ quan sẽ nhận lệnh theo thứ tự sau: $$$[7, 9]$$$.\u003c/p\u003e\u003cp\u003eNếu sĩ quan $$$9$$$ lan truyền một lệnh, các sĩ quan sẽ nhận lệnh theo thứ tự sau: $$$[9]$$$.\u003c/p\u003e\u003cp\u003eĐể trả lời truy vấn thứ $$$i$$$ $$$(u_i, k_i)$$$, hãy xây dựng một chuỗi mô tả thứ tự mà các sĩ quan sẽ nhận lệnh nếu sĩ quan thứ $$$u_i$$$ lan truyền nó. Trả về phần tử thứ $$$k_i$$$ của danh sách được xây dựng hoặc \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e nếu có ít hơn $$$k_i$$$ phần tử trong đó.\u003c/p\u003e\u003cp\u003eBạn nên xử lý các truy vấn một cách độc lập. Một truy vấn không ảnh hưởng đến các truy vấn sau đó.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên của đầu vào chứa hai số nguyên $$$n$$$ và $$$q$$$ ($$$2 \\le n \\le 2 \\cdot 10^5, 1 \\le q \\le 2 \\cdot 10^5$$$) — số lượng sĩ quan trong quân đội Berland và số lượng truy vấn.\u003c/p\u003e\u003cp\u003eDòng thứ hai của đầu vào chứa $$$n - 1$$$ số nguyên $$$p_2, p_3, \\dots, p_n$$$ ($$$1 \\le p_i \u0026lt; i$$$), trong đó $$$p_i$$$ là chỉ số của cấp trên trực tiếp của sĩ quan có chỉ số $$$i$$$. Chỉ huy có chỉ số $$$1$$$ và không có bất kỳ cấp trên nào.\u003c/p\u003e\u003cp\u003eCác dòng tiếp theo mô tả các truy vấn. Truy vấn thứ $$$i$$$ được đưa ra dưới dạng cặp ($$$u_i, k_i$$$) ($$$1 \\le u_i, k_i \\le n$$$), trong đó $$$u_i$$$ là chỉ số của sĩ quan bắt đầu lan truyền một lệnh, và $$$k_i$$$ là chỉ số của sĩ quan cần thiết trong chuỗi lan truyền lệnh.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn $$$q$$$ số, trong đó số thứ $$$i$$$ là sĩ quan ở vị trí $$$k_i$$$ trong danh sách mô tả thứ tự mà các sĩ quan sẽ nhận lệnh nếu nó bắt đầu lan truyền từ sĩ quan $$$u_i$$$. In \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e\" nếu số lượng sĩ quan nhận lệnh ít hơn $$$k_i$$$.\u003c/p\u003e\u003cp\u003eBạn nên xử lý các truy vấn một cách độc lập. Chúng không ảnh hưởng lẫn nhau.\u003c/p\u003e"}},{"title":"Ví dụ","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9 6\n1 1 1 3 5 3 5 7\n3 1\n1 5\n3 4\n7 3\n1 8\n1 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n6\n8\n-1\n9\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}