Cho một cây gồm ~n~ đỉnh, nhiệm vụ của bạn là tìm một centroid, tức là một đỉnh sao cho khi đỉnh đó được chọn làm gốc của cây, mỗi cây con đều có nhiều nhất ~\lfloor n/2 \rfloor~ đỉnh.

Dữ liệu vào

• Dòng đầu chứa một số nguyên ~n~: số lượng đỉnh. Các đỉnh được đánh số từ 1 đến ~n~.

• Tiếp theo là ~n - 1~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~: cho biết có một cạnh nối giữa hai đỉnh ~a~ và ~b~.

Dữ liệu ra

In ra một số nguyên: chỉ số của một đỉnh centroid. Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đỉnh nào.

Ràng buộc

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le a, b \le n~

Ví dụ

Input

5  
1 2  
2 3  
3 4  
3 5

Output

3

Xenia — một lập trình viên, có một cái cây gồm ~n~ đỉnh. Các đỉnh được đánh số từ ~1~ tới ~n~ và có màu đỏ hoặc xanh. Ban đầu, đỉnh ~1~ được tô đỏ, còn tất cả các đỉnh còn lại được tô xanh.

Khoảng cách giữa hai đỉnh ~u~ và ~v~ được định nghĩa là số cạnh trên đường đi ngắn nhất từ ~u~ tới ~v~.

Xenia có các truy vấn thuộc 1 trong 2 loại sau:

• 1 v: tô đỉnh ~v~ thành đỏ.
• 2 v: in khoảng cách nhỏ nhất từ đỉnh ~v~ tới một đỉnh đang có màu đỏ (nếu đỉnh ~v~ đang tô đỏ thì đáp án sẽ là ~0~).

Input

• Dòng đầu: hai số nguyên dương ~n, m~ (~2 \le n \le 2\cdot 10^5~, ~1 \le m \le 10^5~) — số đỉnh và số truy vấn.
• ~n-1~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~u, v~ (~1 \le u, v \le n, u \ne v~), mô tả cạnh của cây.
• Mỗi dòng trong ~m~ dòng tiếp theo là một truy vấn có dạng 1 v hoặc 2 v (~1 \le v \le n~).

Output

• Với mỗi truy vấn loại 2 v, in ra một dòng là câu trả lời cho truy vấn đó.

Ví dụ

Input

7  

1 2  

1 3  

2 4  

3 5  

3 6  

5 7  

6  

1 3  

2 3  

1 5  

2 2  

1 3  

2 3

Output

1  

1  

0

Trong một thành phố hiện đại với những con phố chằng chịt, bạn đang trên hành trình tìm đường trở về nhà. Thành phố có ~n~ đỉnh này được kết nối bởi một mạng lưới ~n - 1~ con đường, nơi mỗi con đường có một đặc điểm riêng – có những con đường ngắn nhưng lại chật hẹp và tắc nghẽn, trong khi có những con đường dài nhưng dễ đi và ít tắc đường hơn.

Mỗi con đường trong thành phố có một trọng số, biểu thị mức độ "khó khăn" để di chuyển, có thể là lượng xe cộ đông đúc, độ dốc của con đường, hay thậm chí là độ dài của đoạn đường cần đi. Bạn không thể muốn đi qua nhiều con đường quá khó, mà muốn tránh những con đường quá dài hoặc quá khó khăn.

Nhiệm vụ của bạn: Bạn cần tìm tất cả những cặp đỉnh trong thành phố sao cho giữa chúng có một đoạn đường đi qua mà:

1. Đoạn đường không quá dài (số lượng con đường mà bạn cần đi qua không vượt quá ~l~.
2. Tổng độ khó khăn của con đường không vượt quá một giới hạn nhất định ~W~, để tránh những con đường quá đông đúc hoặc khó đi.

Mục tiêu là xác định có bao nhiêu cặp đỉnh ~(u, v)~ mà bạn có thể đi từ đỉnh này đến đỉnh kia trong thành phố, sao cho đoạn đường giữa chúng thỏa mãn cả hai điều kiện trên. ~(v < u)~.

Dữ liệu: Vào từ tệp văn bản HOUSE.INP

• Dòng đầu ghi ba số nguyên dương ~n, l, W~ (~1 \le n \le 100000, W \le 1000000000~).

• ~n~ dòng sau, mỗi dòng gồm 2 số ~p_i, w_i~ (~0 \le w_i \le 10000~), là cha của đỉnh ~i+1~ và trọng số của đỉnh đó.

Kết quả: Ghi ra tệp văn bản HOUSE.OUT

• In ra một số nguyên là đáp án kết quả của bài toán.

Ví dụ

Input 1

6 2 17

1 3

2 5

2 13

1 6

5 9

Output 1

9

Input 2

4 4 6

1 3

1 4

1 3

Output 2

4

Anh Anh sống ở vùng thủ đô với ~n~ thành phố đánh số từ ~1~ đến ~n~ và bao gồm ~n - 1~ con đường không có hướng. Mỗi thành phố được gán một giá trị là ~a[i]~. Dữ liệu đảm bảo từ bất kì cặp thành phố nào đều có thể đến với nhau.

Anh Anh định nghĩa khoảng cách từ thành phố ~a~ đến thành phố ~b~ là tổng xor của các giá trị ~a[c]~ với ~c~ là chỉ số của những thành phố nằm trên con đường ngắn nhất từ ~a~ đến ~b~ (bao gồm cả ~a~ và ~b~).

Yêu cầu: Hãy viết chương trình tính tổng khoảng cách giữa các cặp thành phố ~a~ và ~b~ (~a \le b~).

Input

• Dòng đầu tiên gồm một số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a[i]~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa 2 số ~u, v~ có nghĩa là có con đường nối giữa thành phố ~u~ và ~v~.
• (~n \le 100000, ~a[i] \le 1000000~)

Output

• Một số nguyên dương duy nhất là tổng khoảng cách giữa các cặp thành phố ~a~ và ~b~ (~a \le b~).

Ví dụ

Input

3  

1 2 3  

1 2  

2 3

Output

10

Giải thích

• TP 1 đến chính nó có khoảng cách: 1
• TP 2 đến chính nó có khoảng cách: 2
• TP 3 đến chính nó có khoảng cách: 3
• TP 1 đến TP 2 có khoảng cách: ~1 \oplus 2 = 3~
• TP 1 đến TP 3 có khoảng cách: ~1 \oplus 2 \oplus 3 = 0~
• TP 2 đến TP 3 có khoảng cách: ~2 \oplus 3 = 1~

Tổng khoảng cách: ~1 + 2 + 3 + 3 + 0 + 1 = 10~.

Cho một cây có ~n~ đỉnh, nhiệm vụ của bạn là đếm số lượng đường đi khác nhau gồm chính xác ~k~ cạnh.

Input

• Dòng đầu chứa hai số nguyên ~n~ và ~k~: số lượng đỉnh và độ dài của đường đi. Các đỉnh được đánh số từ 1 đến ~n~.
• Tiếp theo là ~n - 1~ dòng, mỗi dòng chứa hai số nguyên ~a, b~ biểu thị có một cạnh nối giữa các đỉnh ~a~ và ~b~.

Output

• In ra một số nguyên: số lượng đường đi có chính xác ~k~ cạnh.

Subtask

• 50% số test có ~n \le 1000~
• 50% số test tiếp theo có ~n \le 100000~

Ví dụ

Input

5 2  

1 2  

2 3  

2 4  

3 5

Output

4

Trong một ngôi làng có ~N~ căn nhà. Mỗi căn nhà chỉ có một người dân sinh sống. Các căn nhà được nối với nhau bằng các con đường; mỗi con đường nối hai căn nhà và có độ dài chính xác 1 km. Từ bất kỳ căn nhà nào cũng có thể đi đến căn nhà khác qua một hoặc nhiều con đường liên tiếp. Tổng cộng có ~N-1~ con đường (tức là đồ thị là một cây).

Một ngày, tất cả người dân đồng loạt chuyển sang một căn nhà khác, sao cho:

• Sau khi chuyển, mỗi căn nhà vẫn có đúng một người (tức là một phép hoán vị các căn nhà),
• Không ai ở lại căn nhà cũ (không có điểm cố định).

Khi di chuyển, mỗi người đi theo đường ngắn nhất giữa nhà cũ và nhà mới.
Hãy tìm tổng độ dài lớn nhất (tính theo km) của các đường đi ngắn nhất đó, xét trên mọi cách hoán vị thỏa điều kiện.

Input

• Dòng đầu: số nguyên ~N~ (~1 < N \le 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, a \ne b~) — có một con đường nối nhà ~a~ và ~b~.

Output

• In ra một số nguyên: tổng độ dài lớn nhất của các đường đi ngắn nhất.

Gợi ý thuật toán

Nếu gọi ~sz_e~ là kích thước (số nhà) của một phía khi cắt cạnh ~e~, thì đáp án bằng: [ \text{ans} \;=\; \sum{e} 2 \cdot \min!\big(sze,\; N - sz_e\big). ] Chỉ cần DFS để tính ~sz_e~ cho từng cạnh rồi cộng lại.

Ví dụ

Input

7  

1 2  

2 3  

2 5  

2 6  

3 4  

4 7

Output

18

Tại một thành phố nọ có tất cả ~n~ thượng nghị sĩ ở trong ~n~ ngôi nhà (đánh số từ 1 đến n), giữa 2 ngôi nhà có một đường đi duy nhất: đường đi trực tiếp hoặc không trực tiếp và đảm bảo tất cả các ngôi nhà đều đến được với nhau.

Mỗi thượng nghị sĩ khi đi từ nhà mình đến thượng viện, phải trả 1 USD khi đi qua một con phố (con phố là đường nối trực tiếp giữa 2 ngôi nhà bất kỳ). Người đứng đầu thượng viện đã nghĩ ra cách làm sao cho số tiền mà các thượng nghị sĩ phải trả là tối thiểu. Vì vậy, ông ra quyết định:

• Có k con phố miễn phí (thượng nghị sĩ sẽ không phải trả tiền khi đi trên con phố này).
• Đặt tòa nhà thượng viện ở 1 trong n ngôi nhà.

Yêu cầu

Hãy viết chương trình tính xem chi phí tối thiểu là bao nhiêu?

Input

• Dòng đầu tiên gồm 2 số nguyên ~n~ và ~k~ tương ứng là số ngôi nhà và số con phố miễn phí.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa 2 số ~u, v~ có nghĩa là có con phố nối ngôi nhà ~u~ và ngôi nhà ~v~ (~1 \le n \le 100000; 0 \le k \le n; 1 \le u, v \le n; u \ne v~).

Output

• Một số duy nhất là chi phí tối thiểu phải trả.

  Ví dụ

Input

13 3  

1 2  

1 3  

2 8  

7 8  

5 7  

7 5  

4 5  

5 6  

8 9  

8 10  

10 11  

10 12  

10 13

Output

11

Giải thích
Có nhiều phương án tối ưu, đây là một phương án: chọn các con phố thứ 4, 5, 9 là 3 con phố miễn phí và đặt thượng viện ở nhà số 8 thì chi phí là 11.

Nhân dịp kỉ yếu lớp 12 của mình, Nhím đã được các bạn tặng 1 dải đèn được trang trí bằng các màu được đánh theo chữ cái của bảng chữ cái La tinh từ a đến z. Có tổng cộng N bóng đèn được nối với nhau bằng (N - 1) dây điện sao cho tất cả các bóng đèn đều được nối với nhau.

Sau khi nhận được dải đèn thì Nhím thắc mắc mức độ đẹp của dải đèn của các bạn tặng được gọi là "trãi lẽ" cho các bạn sao cho "hợp tình hợp lý nhất". Độ đẹp của dải đèn là độ dài lớn nhất của 1 dải đèn trên đường đi từ bóng đèn u đến bóng đèn v sao cho khi trải các màu của bóng đèn theo thứ tự trên đường đi từ u đến v giống với khi trải trên đường đi từ v đến u.

Yêu cầu

Hãy viết chương trình tính xem độ đẹp của dải đèn Nhím được nhận?

Input

• Gồm 1 dòng ghi 1 số nguyên ~N~ (~1 \le N \le 50000~).
• Dòng tiếp theo chứa một xâu gồm ~N~ chữ cái viết thường từ bảng chữ cái Tiếng Anh, trong đó chữ cái thứ i thể hiện màu sắc của bóng đèn thứ i.
• Mỗi dòng trong số (N - 1) dòng tiếp theo chứa hai số nguyên ~x~ và ~y~ (~1 \le x, y \le N, x \ne y~), cho biết bóng đèn x và bóng đèn y được nối trực tiếp bởi dây điện.

Output

• Một số duy nhất là độ đẹp của dải đèn Nhím được nhận.

Ví dụ

Input

4  

aabb  

1 2  

2 3  

3 4

Output
2

Giải thích
Dải đèn có độ đẹp lớn nhất là (1, 2).

Sau khi thi học xong lớp 12, Nhím đã đỗ vào trường đại học mà mình mong muốn ở trên HN. Nhím rất háo hức khi được học ở một thành phố lớn và đông đúc, vì vậy anh ấy đã lên tham quan trường rất sớm và đi dạo tìm hiểu nơi mà sẽ gắn bó trong 4 năm tới.

Không may một điều bất trắc thì với sở thích kì lạ của mình thì anh ấy không thể biết được nơi nào sẽ là nơi thích hợp nên Nhím muốn nhờ bạn giúp anh ấy tìm độ tốt của các phòng trọ để anh ấy dễ dàng lựa chọn nhé.

Có N phòng trọ còn phòng trống, có N – 1 đường đi để có thể từ một phòng trọ để đi qua hết N – 1 phòng trọ còn lại. Lí do chỉ có N – 1 là chung ta ở trong các ô nhưng tuyến đường không thể đi được trên thành phố Hà Nội.

Mỗi phòng trọ được ghi một chữ cái từ "a" đến "t" trên bảng chữ cái la tinh.

Độ đẹp của một phòng trọ được tính là số phòng trọ u và sao cho trên đường đi từ u đến v đi qua phòng trọ mình đang xét và khi trải các chữ cái của các phòng trọ đường đi từ u đến v có thể sắp xếp được thành palindrom.

Yêu Cầu : Hãy viết chương trình tính xem độ đẹp của mỗi phòng trọ?

INPUT :

• Gồm 1 dòng ghi 1 số nguyên ~N~ (~1 \le N \le 200000~).
• Mỗi dòng trong số ~(N-1)~ dòng tiếp theo chứa hai số nguyên ~x~ và ~y~ (~1 \le x, y \le N, \; x \ne y~), cho biết đường đi nối trực tiếp 2 phòng trọ ~x~ và ~y~.
• Dòng tiếp theo chứa một mảng gồm ~N~ chữ cái viết thường trong khoảng "~a~"" đến "~t~"" trên bảng chữ cái La tinh.

OUTPUT :

• ~N~ số được cách nhau bằng dấu cách là độ đẹp của mỗi phòng trọ.

Ví dụ

Input

5  

1 2  

2 3  

2 4  

3 5  

abcbb

Output

1 3 4 3 3