Bạn vừa được HCV IOI nên thầy Tùng quyết định thưởng cho bạn. Thầy cho bạn một cây có ~n~ đỉnh. Với mỗi đỉnh ~i~ cho 2 số ~l_i \le r_i~. Việc bạn cần làm là chọn một số ~v_i~ ở mỗi đỉnh sao cho ~l_i \le v_i \le r_i~ và số tiền được thưởng (tính bằng triệu VND) sẽ là tổng của ~|v_i - v_j|~ với toàn bộ các cạnh ~(i, j)~ vô hướng của cây. Hãy in ra số tiền nhiều nhất bạn có thể được thầy thưởng.

Input

• Dòng đầu tiên là số nguyên dương ~n \le 10 ^ 5~ là số đỉnh của cây.
• ~n~ dòng tiếp theo mỗi dòng ~i~ gồm 2 số ~l_i \le r_i \le 10^9~ là chỉ số của đỉnh thứ ~i~.
• ~n - 1~ dòng tiếp theo mỗi dòng là 2 số ~u, v~ là cạnh của cây.

Output

• In ra một số là số tiền lớn nhất bạn có thể được thưởng.

Subtasks

• Subtask 1: ~n \leq 20~.
• Subtask 2: Với mỗi ~i < n~, tồn tại một cạnh ~i~ với ~i + 1~.
• Subtask 3: Không có điều kiện gì thêm.

Sample Test

Input:

3
1 3
4 6
7 9
1 2
2 3

Output:

8

Cho một cây có ~n~ đỉnh, đỉnh ~i~ có số ~A_i~ viết trên. Tìm một đường đi đơn có tổng lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.
• ~n - 1~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u, v~, có cạnh giữa ~u~ và ~v~.

Output

• In ra tổng lớn nhất.

Constraints

• ~1 \le n \le 10^5~.
• ~0 \le |A_i| \le 10^9~.

Example

Sample Input 1

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

Sample Output 1

7

Cho một cây gồm ~n~ đỉnh có gốc là ~1~.

Bạn được cho ~m~ truy vấn, truy vấn thứ ~i~ như sau:

• Truy vấn bao gồm ~k_i~ số đỉnh phân biệt ~v_{1},v_{2},...,v_{k_i}~. Bạn cần kiểm tra xem liệu có tồn tại một đường đi từ gốc tới một đỉnh ~u~ sao cho mỗi đỉnh trong ~k_i~ đỉnh đã cho đều thuộc vào đường đi này hoặc có khoảng cách bằng ~1~ với một số đỉnh trên đường đi này.

Input

• Dòng đầu chứa hai số nguyên ~n, m~ ~(n \le 10^5, m \le 2\times 10^5)~.
• ~n-1~ dòng sau, mỗi dòng sau gồm hai số ~u,v~ miêu tả cạnh ~(u,v)~ của cây,
• ~m~ dòng sau miêu tả ~m~ truy vấn có dạng:
  • Đầu tiên là một số nguyên dương ~k_i~ miêu tả số đỉnh. Tiếp theo là ~k_i~ đỉnh phân biệt miêu tả truy vấn.
• Tổng ~k_i~ trong tất cả các truy vấn không vượt quá ~4 \times 10^5~.

Output

• Với mỗi kết quả, nếu có đường đi từ gốc thỏa mãn thì in ra "1", ngược lại in ra "0".

Sample Input 1

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

Sample Output 1

1
1
1
1
0
0

TR là một hệ thống trao đổi dữ liệu trực tiếp giữa các máy tính đang được thử nghiệm tại trường ~X~. Trường có ~N~ máy tính được đánh số từ ~1~ đến ~N~. Các máy tính đều sử dụng hệ thống TR và được kết nối với nhau theo đồ thị dạng cây.

Ban đầu, hệ thống có một tệp dữ liệu đang được lưu trữ bởi một hoặc hai máy tính. Trường muốn truyền tệp này đến tất cả các máy tính khác trong hệ thống. Cơ chế truyền dữ liệu của hệ thống TR như sau: cứ một phút, mỗi máy tính trong hệ thống chỉ có thể truyền dữ liệu đến duy nhất một máy tính khác được kết nối trực tiếp với nó.

Yêu cầu: Cho số hiệu của các máy tính đang lưu trữ tệp dữ liệu ở thời điểm ban đầu. Hãy tính thời gian tối thiểu để tất cả các máy tính trong hệ thống nhận được tệp dữ liệu.

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

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \lt N \le 10^5)~ là số lượng máy tính;
• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên khác nhau ~x~ và ~y~ ~(1 \le x, y \le N)~ mô tả số hiệu của hai máy tính được kết nối trực tiếp;
• Dòng tiếp theo chứa số ~M~ ~(1\le M\le 2)~ là số lượng máy tính đang lưu trữ tệp dữ liệu ở thời điểm ban đầu;
• Dòng tiếp theo chứa ~M~ số nguyên dương mô tả số hiệu của các máy tính đang lưu trữ tệp dữ liệu ở thời điểm ban đầu;

Dữ liệu ghi ra tệp văn bản TDL.OUT:

Gồm một số nguyên là thời gian tối thiểu hoàn thành công việc.

Ví dụ

Input

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

Output

3

Giải thích

Ban đầu máy ~1~ lưu trữ tệp dữ liệu.

Phút thứ ~1~: máy ~2~ nhận được tệp dữ liệu.

Phút thứ ~2~: máy ~3~ và ~5~ nhận được tệp dữ liệu.

Phút thứ ~3~: máy ~4~ và ~6~ nhận được tệp dữ liệu.

Input

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

Output

2

Giải thích

Ban đầu máy ~1~ và ~2~ lưu trữ tệp dữ liệu.

Phút thứ ~2~: máy ~3~ và ~5~ nhận được tệp dữ liệu.

Phút thứ ~3~: máy ~4~ và ~6~ nhận được tệp dữ liệu.

Minh hoạ

Ràng buộc

• Có ~25\%~ số test ứng với ~25\%~ số điểm có ~N\le 20~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~M=1~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~M=2; N\le 1000~;
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm không có ràng buộc gì thêm.

Một công ty gồm ~N~ người được đánh số từ ~1~ tới ~N~. Tổng giám đốc của công ty được đánh số là ~1~, mỗi người từ ~2~ tới ~N~ có đúng một cấp trên trực tiếp của mình.

Nếu ~i~ là cấp trên trực tiếp của ~j~, ta gọi ~i~ là quản lý của ~j~. Nếu ~i~ là quản lý của ~j~ thì ~i~ cũng là quản lý của những người mà ~j~ quản lý. Không có trường hợp ~i~ là quản lý của ~j~ đồng thời ~j~ là quản lý của ~i~.

Công ty có chế độ lương thưởng rất đặc biệt, người thứ ~i~ có lương là ~a_i~, người cấp dưới có thể có lương cao hơn người quản lý.

Công ty muốn tổ chức một sự kiện cho toàn bộ công ty. Nhưng nếu hai người ~u~ và ~v~ tham gia, trong đó ~u~ là quản lý của ~v~ mà lương của ~u~ không cao hơn lương của ~v~ ~(a_u \le a_v)~ thì sẽ gây ra bất hoà. Công ty muốn chọn ra được nhiều người nhất tham gia sự kiện mà không có sự bất hoà nào.

Phòng tổ chức sự kiện đã lên ~Q~ giả định như sau: Xét người ~u \ (1 \le u \le N)~, chọn ra một số người mà ~u~ là quản lý (có thể chọn hoặc không chọn ~u~) để tham gia sự kiện sao cho:

• Tổng số người được chọn là lớn nhất;
• Không có sự bất hoà nào giữa những người được chọn.

Yêu cầu: Với mỗi giả định, in ra số người nhiều nhất có thể chọn để tham gia sự kiện.

Dữ liệu vào từ file văn bản CONGTY.INP:

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 2 \times 10^5)~;
• Dòng thứ hai gồm ~N~ số nguyên dương, số thứ ~i~ là ~a_i~ mô tả mức lương của người thứ ~i~ ~(1 \le a_i \le 10^9)~;
• Dòng thứ ba gồm ~N - 1~ số nguyên dương, số thứ ~i~ là ~p_i~ mô tả ~p_i~ là cấp trên trực tiếp của ~i+1~ ~(1 \le p_i \le N)~;
• ~Q~ dòng sau, dòng thứ ~i~ gồm một số nguyên dương ~u_i \ (1 \le u_i \le N)~, mô tả giả định thứ ~i~.

Kết quả ghi ra file văn bản CONGTY.OUT:

Với mỗi giả định, in ra kết quả tương ứng.

Ví dụ

Input

6 3
8 4 2 7 1 3
1 1 3 2 3
1
3
4

Output

5
2
1

Giải thích

Hình vẽ minh hoạ như Hình 3.

• Với giả định thứ nhất, chọn các nhân viên: ~1, 2, 5, 4, 6~;
• Với giả định thứ hai, chọn các nhân viên: ~4, 6~;
• Với giả định thứ ba, chọn nhân viên: ~4~.

Input

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

Output

4
6

Giải thích

• Với giả định thứ nhất, chọn các nhân viên: ~3, 4, 5, 6~;
• Với giả định thứ hai, chọn các nhân viên: ~1, 2, 3, 4, 5, 6~.

Ràng buộc

• Có ~15\%~ số test ứng với ~15\%~ số điểm của bài thoả mãn: ~N \le 15; \ Q = 1~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: nếu ~u~ là quản lý của ~v~ thì ~a_u > a_v~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm của bài thoả mãn: ~i~ là cấp trên trực tiếp của ~i+1~ ~(1 \le i \le N)~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm của bài thoả mãn: ~N \le 1000; \ a_i \le 100~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~N \le 10^5; \ a_i \le 100~;
• ~15\%~ số test còn lại ứng với ~15\%~ số điểm của bài không có ràng buộc gì thêm.

Trong một trò chơi, có một robot di chuyển trên một bản đồ dạng cây gồm ~𝑁~ ngọn núi và ~𝑁 − 1~ con đường nối các ngọn núi. Mỗi ngọn núi có ~𝐾~ kho báu và mỗi con đường nối hai ngọn núi đều có ~2~ kho báu. Quy tắc di chuyển của robot như sau:

• Robot chọn một ngọn núi để xuất phát~;~
• Tại mỗi lượt di chuyển qua một ngọn núi hoặc một con đường, robot khai thác để lấy một kho báu và di chuyển tiếp~;~
• Robot có thể di chuyển từ ngọn núi ~𝑢~ đến ~𝑣~ nếu thoả mãn cả hai điều kiện: con đường nối ngọn núi ~u~ đến ngọn núi ~𝑣~ còn lại ít nhất một kho báu và ngọn núi ~𝑣~ còn lại ít nhất một kho báu. Nếu không còn kho báu, ngọn núi và con đường sẽ bị phá huỷ, robot không thể di chuyển đến.

Yêu cầu: Em hãy tính xem robot có thể đi qua nhiều nhất bao nhiêu con đường.

Dữ liệu nhập vào từ file văn bản TKB.INP:

• Dòng đầu tiên chứa hai số nguyên dương ~𝑁, 𝐾~ ~(𝑁 ≤ 10^5; \ 𝐾 ≤ 10^9);~
• ~𝑁 − 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~𝑢, 𝑣~ ~(1 ≤ 𝑢, 𝑣 ≤ 𝑁)~ mô tả con đường nối hai ngọn núi.

Kết quả ghi ra file văn bản TKB.OUT:

In ra một số nguyên là số lượng con đường nhiều nhất mà robot đi qua.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 1;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 20;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 300; \ 𝐾 = 2;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 1000;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

4

Giải thích

Robot có thể di chuyển theo thứ tự các ngọn núi: ~3 − 2 − 1 − 6 − 7~. Robot đi qua 4 con đường.

Input

4 3
1 2
2 4
2 3

Output

6

Giải thích

Robot có thể di chuyển theo thứ tự các ngọn núi: ~1 − 2 − 4 − 2 − 3 − 2 − 1~. Robot đi qua ~6~ con đường.