Cho một cây gồm ~n~ nút, các nút được đánh số từ ~1~ đến ~n~.

Một nút được gọi là trọng tâm của cây nếu khi xóa nút đó khỏi cây, mọi thành phần liên thông còn lại đều có số nút không vượt quá ~\left\lfloor \frac{n}{2} \right\rfloor~.

Yêu cầu

Hãy tìm một trọng tâm của cây.

Nếu có nhiều đáp án, có thể in ra bất kỳ đáp án nào.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^5)~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a, b~ ~(1 \le a, b \le n)~, mô tả một cạnh nối hai nút ~a~ và ~b~.

Output

• In ra một số nguyên duy nhất là chỉ số của một nút trọng tâm.

Sample Input

5
1 2
2 3
3 4
3 5

Sample Output

3

Giải thích ví dụ

Nếu xóa nút ~3~, cây tách thành ba thành phần có kích thước lần lượt là ~2~, ~1~ và ~1~.

Tất cả đều không vượt quá ~\left\lfloor \frac{5}{2} \right\rfloor = 2~, nên nút ~3~ là một trọng tâm.

Bạn Tuyết, như cái tên của bạn, rất thích vẻ đẹp của các bông tuyết. Bạn có thể dành hàng giờ chỉ để ngắm chúng.

Khác với thế giới bình thường, nơi mà các bông tuyết đa phần có 6 nhánh với cấu trúc đối xứng và phức tạp; bông tuyết ở thế giới của bạn Tuyết có hình dạng là một cây (đồ thị vô hướng không có chu trình) gồm có ~n đỉnh, được đánh số từ ~1~ tới ~n~. Đỉnh của cây được đánh số ~1~.

Tuyết muốn chọn trọng tâm của một nhánh con (hay còn gọi là cây con) của bông tuyết để cân bằng. Tuy nhiên, bạn ấy chưa biết nên chọn nhánh con nào. Bạn được biết ~q~ lựa chọn nhánh con sơ bộ của Tuyết, hãy tìm một trọng tâm của từng nhánh con đó cho Tuyết nhé!

Ta gọi đỉnh ~u~ là tổ tiên của đỉnh ~v~, hay đỉnh ~v~ là hậu duệ của đỉnh ~u~, nếu trên đường đi trực tiếp từ đỉnh ~v~ đến gốc ~1~ có chứa đỉnh ~u~. Đỉnh ~u~ được gọi là cha của đỉnh ~v~ nếu ~u~ là tổ tiên của ~v~ và ~u~ kề ~v~. Nhánh con của một đỉnh ~u~ bao gồm chính đỉnh ~u~ và các hậu duệ của đỉnh ~u~. Nhánh con cũng có hình dạng cây.

Trọng tâm của một cây (hoặc một nhánh con) là đỉnh mà nếu như xóa đỉnh đó đi khỏi cây, thì trong số các cây bị tách rời, cây lớn nhất có số đỉnh nhiều bằng nhiều nhất một nửa số đỉnh của cây (hoặc nhánh con) ban đầu.

Input

• Dòng đầu tiên chứa hai số ~n~ và ~q~ ~(2 \leq n \leq 5 \times 10^{5}, 1 \leq q \leq 5 \times 10^{5})~ - số đỉnh của bông tuyết, và số nhánh con trong danh sách sơ bộ của Tuyết.
• Dòng thứ hai chứa ~n - 1~ số ~p_{2}, p_{3}, \ldots, p_{n}~ ~(1 \leq p_{i} \leq n~, với ~p_i~ cho biết chỉ số đỉnh cha của đỉnh ~i~.
• ~q~ dòng tiếp theo, mỗi dòng gồm một số duy nhất ~v_{i}~ ~(1 \leq v_{i} \leq n)~, cho biết đỉnh đại diện cho nhánh con cần tìm trọng tâm.

Output

Với mỗi truy vấn, in ra một dòng chỉ số của đỉnh trọng tâm ứng với nhánh con của đỉnh được hỏi. Nếu có nhiều đỉnh thỏa mãn, in ra bất kỳ đáp án hợp lệ nào. Có thể đảm bảo rằng, mỗi nhánh con đều có ít nhất một đỉnh trọng tâm.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~n, q \leq 500~
• Subtask ~2~ (~30\%~ số điểm): ~n, q \leq 5000~
• Subtask ~3~ (~20\%~ số điểm): ~n, q \leq 10^{5}~
• Subtask ~4~ (~20\%~ số điểm): không có ràng buộc gì thêm

Input

10 5 
10 10 1 4 3 5 2 3 5
4
6
10
1
5

Output

10
6
3
10
10

Vương quốc Alpha là một tiểu vương quốc mới được thành lập và đang trên đà phát triển. Quốc vương của họ - Aleck - quyết định chia nhỏ vương quốc thành ~n~ tỉnh thành để dễ dàng kiểm soát hơn. Để tiết kiệm chi phí, nhà vua chỉ cho xây dưng ~n - 1~ con đường kết nối giữa ~2~ tỉnh thành khác nhau, tuy nhiên vẫn phải đảm bảo ~2~ tỉnh thành bất kỳ phải đến được với nhau.

Nhà vua đang gấp rút đề cử ra ~n~ người giám sát, mỗi người sẽ có nhiệm vụ giám sát hoạt động của ~1~ tỉnh thành. Hơn nữa, nhà vua muốn gán cấp bậc của mỗi người giám sát là ~1~ chữ cái từ 'A' đến 'Z' biểu thị cho mức độ quan trọng của tỉnh thành đó. Bậc 'A' là cao nhất, còn bậc 'Z' là thấp nhất.

Việc gán cấp bậc cho mỗi người giám sát còn phải đảm bảo được rằng: Nếu tồn tại ~2~ thành phố có người giám sát là cùng bậc, thì đường đi kết nối giữa ~2~ thành phố đó phải đi qua ít nhất ~1~ thành phố có người giám sát có cấp bậc cao hơn. Điều này cho thấy được tầm quan trọng của những người giám sát bậc cao.

Đề xuất cho nhà vua Aleck ~1~ cách để thực hiện việc đó, hoặc thông báo cho nhà vua biết điều đó là bất khả thi.

Input

Dòng ~1~: Gồm một số nguyên ~n~ ~(1 \le n \le 10^5)~ là số lượng tỉnh thành của vương quốc Alpha.

~n - 1~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~a, b~ ~(1 \le a, b \le n; a \ne b)~ là một con đường ~2~ chiều kết nối giữa ~2~ tỉnh thành ~a~ và ~b~.

Output

Nếu có ~1~ cách thỏa mãn, in ra ~n~ chữ cái in hoa, chữ cái thứ ~i~ đại diện cho cấp bậc của người giám sát cho tỉnh thành ~i~.

Nếu không, in ra 'Impossible!'.

Scoring

Subtask ~1~ ~(30\%~ số điểm~):~ Mỗi tỉnh thành chỉ được kết nối với tối đa ~2~ tỉnh thành khác.

Subtask ~2~:~(30\%~ số điểm~):~ Khoảng cách tối đa giữa ~2~ tỉnh thành bất kỳ không vượt quá ~50~.

Subtask ~3~:~(40\%~ số điểm~):~ Không có điều kiện gì thêm.

Sample Input 1

4
1 2
1 3
1 4

Sample Output 1

A B B B

Sample Input 2

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Sample Output 2

D C B C A D C B C D

Cây là một đồ thị vô hướng liên thông mà không có chu trình. Giữa hai đỉnh bất kì trên cây, có một và chỉ một đường đi đơn. Ta định nghĩa khoảng cách giữa hai đỉnh là số cạnh trên đường đi đơn duy nhất này.

Cho một cây gồm n đỉnh, các đỉnh được đánh số từ 1 đến ~n~. Cho một số nguyên ~k~, hãy đếm số cặp đỉnh (u, v) trên cây sao cho khoảng cách giữa ~u~ và ~v~ là ~k~. Hai cặp đỉnh (u, v) và (v, u) được tính là giống nhau.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ là số đỉnh của cây và số nguyên ~k~ (~1 \le k < n \le 3 * 10^5~).
• Trong ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (~1 \le u, v \le n~) cho biết trên cây có một cạnh nối hai đỉnh u và v.

Output

• In ra một số nguyên duy nhất là số cặp đỉnh (u, v) sao cho khoảng cách từ u đến v là k.

Subtask

• 25% ~n \le 3000~
• 25% cây đường thẳng
• 25% ~k \le 100~
• 25% không giới hạn gì thêm

Example

Sample Input

7 3
3 7
3 2
2 1
2 4
1 5
1 6

Sample Output

6

Note

• Các cặp đỉnh có khoảng cách bằng 3 là: (7, 4), (7, 1), (4, 5), (4, 6), (3, 5) và (3, 6).

Cho một cây gồm ~N~ đỉnh, được đánh số từ ~1~ đến ~N~.

Ban đầu tất cả các đỉnh đều có màu đen.

Có ~Q~ truy vấn thuộc một trong hai loại:

• 0 u: đổi màu đỉnh ~u~. Nếu ~u~ đang đen thì đổi thành trắng, nếu ~u~ đang trắng thì đổi thành đen.
• 1 u: hỏi khoảng cách nhỏ nhất từ đỉnh ~u~ tới một đỉnh trắng bất kỳ.

Nếu không có đỉnh trắng nào trong cây, đáp án của truy vấn loại 1 là -1.

Input

• Dòng đầu tiên chứa số nguyên ~N~.
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~, mô tả một cạnh của cây.
• Dòng tiếp theo chứa số nguyên ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một truy vấn có dạng 0 u hoặc 1 u.

Output

• Với mỗi truy vấn loại 1, in ra đáp án trên một dòng.

Ràng buộc

• ~1 \le N \le 100000~
• ~1 \le Q \le 100000~
• ~1 \le u, v \le N~
• Các cạnh tạo thành một cây.

Subtask

Sample Input

5
1 2
1 3
3 4
3 5
6
1 1
0 4
1 1
1 5
0 4
1 5

Sample Output

-1
2
2
-1

Giải thích

Ban đầu không có đỉnh trắng nên truy vấn 1 1 có đáp án -1.

Sau truy vấn 0 4, đỉnh ~4~ chuyển sang màu trắng.

• ~dist(1, 4) = 2~
• ~dist(5, 4) = 2~

Sau truy vấn 0 4 lần nữa, đỉnh ~4~ trở lại màu đen, không còn đỉnh trắng nào trong cây.

Đây là bài toán giao tiếp với máy chấm (Interactive problem)

Jury có một con số ~n~ bí mật. Điều duy nhất bạn biết về con số này là ~1 \leq n \leq 2 \times 10^9~. Jury và bạn sẽ chơi một trò chơi như sau: Bạn sẽ được chọn một số bất kỳ và nói cho [Jury nghe số đó. Jury sẽ cho bạn biết con số của bạn lớn hơn, nhỏ hơn, hay bằng ~n~. Hãy đoán xem ~n~ là số nào trong không quá ~31~ câu hỏi.

Cách Thức Giao Tiếp

Mỗi lượt, bạn sẽ in ra một số ~x~ trên một dòng (~1\leq x \leq 2 \times 10^9~). Máy tính sẽ đọc ~x~ và in ra màn hình một chuỗi tương ứng với các trường hợp sau:

• "BIGGER" nếu ~n > x~
• "SMALLER" nếu ~n < x~
• "HOLA" nếu ~n = x~.

Lưu ý:

• Chuỗi mà máy in ra màn hình không có dấu "
• Nếu các bạn in ra một output không hợp lệ (không phải là một số, số ngoài đoạn ~[1, 2 \times 10^9]~ thì nhiều khả năng bị TLE.
• Sau khi in mỗi số, bạn phải xuống dòng (ví dụ in endl trong C++)
• Khi in ra một dòng, các bạn phải flush output bằng cách cout.flush hoặc dùng endl thay vì \n

Example

Con số bí mật trong test này là 5.

Đây là một bài toán interactive.

Cho một cây gồm ~N~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~N~. Có một đỉnh bí mật ~S~ do judge chọn. Nhiệm vụ của bạn là tìm ra đỉnh ~S~.

Bạn được hỏi tối đa ~12~ lần.

Input ban đầu

Chương trình của bạn nhận:

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

Đỉnh bí mật ~S~ không được cho trong input.

Interaction

Để hỏi một đỉnh ~u~, hãy in ra:

? u

Sau đó flush output.

Judge sẽ trả về một số nguyên:

• ~0~ nếu ~u = S~.
• Ngược lại, judge trả về một đỉnh ~v~ kề với ~u~, sao cho ~v~ nằm trên đường đi từ ~u~ tới ~S~.

Nói cách khác, nếu bạn đang đứng ở ~u~, judge chỉ cho bạn hướng đầu tiên cần đi để tới đỉnh bí mật.

Khi đã tìm được đáp án, hãy in ra:

! S

Sau đó flush output và kết thúc chương trình.

Nếu chương trình hỏi quá ~12~ lần, hỏi đỉnh không hợp lệ, hoặc in đáp án sai, kết quả sẽ là Wrong Answer.

Ràng buộc

• ~2 \le N \le 1000~
• Cây gồm đúng ~N - 1~ cạnh.
• Mỗi cạnh nối hai đỉnh khác nhau.
• Input luôn tạo thành một cây liên thông.

Subtask

Ví dụ interaction

Giả sử cây có ~5~ đỉnh:

1 - 2 - 3 - 4 - 5

và đỉnh bí mật là ~S = 4~.

Một interaction hợp lệ có thể là:

Ghi chú

Sau mỗi lần in query hoặc đáp án, cần flush output. Trong C++, có thể dùng:

cout << "? " << u << endl;

hoặc:

cout << "? " << u << '\n';
cout.flush();

Lệnh endl tự động flush output.

Vương quốc có ~n~ thành phố và ~n-1~ con đường hai chiều, đảm bảo đi lại giữa mọi cặp thành phố. Thành phố x được gọi là quản lý ~y~ nếu ~x~ nằm trên đường đi đơn từ ~y~ đến 1. Sản lượng lương thực tại thành phố ~x~ là ~w_x~. Quốc vương muốn chọn ra một đỉnh để xây dựng kho dự trữ, chi phí vận chuyển lương thực nếu xây dựng kho dự trữ tại ~u~ là ~∑_{v=1}^n {w_v×d(v,u)}~ với ~d(v,u)~ là số cạnh trên đường đi đơn từ ~v~ đến ~u~.

Có ~Q~ thay đổi cho sản lượng được báo cáo, mỗi thay đổi có dạng ~1\ u\ c~ hoặc ~2\ u\ c~ tương ứng là tăng ~w_u~ lên ~c~ đơn vị hoặc tăng ~w_v~ lên ~c~ đơn vị với mọi ~v~ quản lý bởi ~u~. Sau mỗi thay đổi, cần tìm đỉnh ~u~ để xây dựng kho dữ trữ sao cho tổng chi phí vận chuyển lương thực là nhỏ nhất, nếu có nhiều ~u~ như vậy thì chọn ~u~ nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~Q~;
• Dòng thứ hai chứa ~n~ số ~w_1,w_2,...,w_n~;
• Mỗi dòng trong số ~n - 1~ dòng tiếp theo chứa hai số ~u\ v~ mô tả một cạnh của cây;
• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa ba số ~t\ u\ c~ mô tả một thay đổi

Output

• Ghi ~Q~ dòng là chỉ số của đỉnh được chọn sau thay đổi thứ ~Q~.

Scoring

• Trong tất cả các test: ~n,Q ≤ 10^5; 1 ≤ w_i ≤ 10^6; |c| ≤ 10^6.~
• Có 12% số test với ~n,Q ≤ 5000~;
• Có 16% số test có cạnh nối từ ~x~ đến ~x - 1~ với mọi ~2 ≤ x ≤ n;~
• Có 16% số test có cạnh nối từ ~x~ đến ~[x/2]~ với mọi ~2 ≤ x ≤ n;~
• Có 20% số test không có thay đổi loại 2;
• Có 36% số test với ràng buộc gốc. uộc gốc

Sample Input 1

5 3 
1 3 2 1 4 
1 2 
1 3 
2 4 
2 5 
1 2 2 
2 3 4 
1 1 5

Sample Output 1

2 
2 
1