Cho một cây có ~n~ đỉnh, hãy xác định số lượng cạnh lớn nhất có thể xóa bỏ để toàn bộ các vùng liên thông còn lại có kích thước chẵn.

Input

• Dòng đầu tiên chứa số nguyên dương ~n \le 10^5~.
• ~n - 1~ dòng tiếp theo chứa 2 số ~u, v (u, v \le n)~ là các cạnh của cây.

Output

• In ra một số nguyên số cạnh có thể xóa
• Nếu không thể có cách cắt thỏa mãn, in ra -1.

Sample Test 1

Input:

4
2 4
4 1
3 1

Output:

1

Sample Test 2

Input:

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

Output:

4

Cho một cây vô hướng không trọng số gồm ~n~ đỉnh.

Với mọi ~1 \le u < v \le n~, gọi ~S(u,v)~ là tập các cạnh nằm trong đường đi ngắn nhất từ ~u~ tới ~v~.

Với mỗi cạnh ~(x,y)~ của cây, hãy đếm xem cạnh đó xuất hiện trong bao nhiêu tập ~S(u,v)~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x,y~ miêu tả cạnh của cây.

Constraint

• ~1 \le n \le 10^5~

Subtask

• Subtask ~1~ ~(40\%)~: ~n \le 2000~.
• Subtaks ~2~ ~(60\%)~: Không có điều kiện gì thêm.

Output

• In ra kết quả cần tính của mỗi cạnh ~(x,y)~ theo thứ tự Input.

Sample Input 1:

4
1 2
1 3
3 4

Sample Output 1:

3
4
3

Cho cây ~n~ đỉnh gồm ~n-1~ cạnh có gốc tại đỉnh ~1~. Đỉnh thứ ~i~ có giá trị là ~a_i~.

Đối với mỗi đỉnh ~u~, ta cần phải tính độ đẹp của đường đi xuất phát từ gốc là đỉnh ~1~ tới ~u~. Độ đẹp trên đường đi này được tính như sau:

• Ta có thể chọn tối đa một đỉnh ~v~ bất kì thuộc đường đi từ ~1~ tới ~u~, sau đó gán giá trị ~a_v = 0~.
• Tiếp theo, tính giá trị ~X =~ ước chung lớn nhất theo giá trị của các đỉnh thuộc đường đi từ ~1~ tới ~u~.
• Độ đẹp của đường đi từ ~1~ tới ~u~ là cách thay đỉnh tốt nhất (hoặc có thể giữ nguyên giá trị các đỉnh) sao cho giá trị ~X~ thu được là lớn nhất.

Với mỗi ~u~ từ ~1~ tới ~n~, bạn cần tính được độ đẹp của đường đi ~(1,u)~, lưu ý các truy vấn ở đây là độc lập, nghĩa là bạn không thay đổi thực sự một giá trị nào cả.

Input

• Dòng đầu chứa số nguyên ~n~ ~( n \le 2 \times 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương miêu tả dãy ~a~ ~(1 \le a_i \le 2 \times 10^5)~
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~ ~(1≤u,v≤n; u≠v;)~ mô tả một cạnh của cây nối hai đỉnh ~u_i~ và ~v_i~.

Output

• In ra ~n~ số nguyên dương là độ đẹp của đường đi ~(1,u)~ với ~u \in [1,n]~

Subtask

• Subtask ~1~: ~n \le 2000 ~. ~(50\%)~
• Subtask ~2~: Không có giới hạn gì thêm. ~(50\%)~

Sample Input 1

3
6 2 3
1 2
1 3

Sample Output 1

6 6 6

Cho một cây vô hướng không trọng số gồm ~n~ đỉnh.

Ban đầu, các cạnh được gán trọng số bằng ~0~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(a,b)~, tức là sẽ tăng các cạnh trên đường đi ngắn nhất từ đỉnh ~a~ tới đỉnh ~b~ lên ~1~ đơn vị.

Sau ~q~ truy vấn, hãy in ra giá trị của từng cạnh.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x,y~ miêu tả cạnh của cây.
• Dòng sau gồm số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng là hai số nguyên dương ~(a,b)~ miêu tả truy vấn.

Constraint

• ~1 \le n,q \le 10^5~

Subtask

• Subtask ~1~ ~(40\%)~: ~n,q \le 2000~.
• Subtaks ~2~ ~(60\%)~: Không có điều kiện gì thêm.

Output

• In ra kết quả cần tính của mỗi cạnh ~(x,y)~ theo thứ tự Input.

Sample Input 1:

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

Sample Output 1:

1
2
1

Cho một cây vô hướng ~n~ đỉnh. Trên mỗi đỉnh ~i~ sẽ có một trọng số nguyên ~a_i~. Định nghĩa ~g(u,v)~ là giá trị lớn nhất của trọng số các đỉnh trên đường đi ngắn nhất từ ~u~ đến ~v~. Hãy tính tổng ~g(u,v)~ với mọi cặp ~(1 \le u < v \le n)~.

Input:

• Dòng đầu là số nguyên dương ~n~. ~(2 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên ~a_i. (|a_i| <= 10^6)~.
• ~n-1~ dòng sau mỗi dòng gồm 2 số nguyên ~u,v~ miêu tả cạnh nối giữa 2 đỉnh ~u,v~.

Output:

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

Subtasks

• Subtask 1: ~n \leq 5000~.
• Subtask 2: Không có điều kiện gì thêm.

Sample Test

Input:

3
3 2 4
1 2
1 3

Output:

11

Giải thích:

Ta có : ~g(1,2) + g(1,3) + g(2,3) = 3 + 4 + 4 = 11.~

Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~, trọng số của đỉnh thứ ~i~ là ~a_i~. Gọi ~S(i)~ là dãy các trọng số của các đỉnh trên đường đi từ ~1~ tới ~i~.

Với mỗi ~i~, hãy tìm độ dài dãy con tăng dài nhất của ~S(i)~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả trọng số của các đỉnh ~(1 \le a_i \le 10^9)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.

Output

• In ra ~n~ số nguyên là độ dài của dãy con tăng dài nhất của ~S(i)~.

Subtask

• Subtask ~1~: ~a_i \le 100~. ~(30\%)~
• Subtask ~2~: Không có đỉnh nào có quá hai cạnh nối. ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

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

Sample Output 1

1
2
3
3
4
4
5
2
2
3

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.

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm ~n~ đỉnh và ~n-1~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh thứ ~i~ có trọng số là ~a_i~. Lưu ý dãy ~a~ gồm các phần tử đôi một khác nhau.

Bạn được nhận thêm hai giá trị nguyên không âm ~c~ và ~d~. Xét một đường đi đơn ~P~ trên cây, gọi ~V~ là tập đỉnh trên đường đi này. Chúng ta định nghĩa độ đẹp của ~P~ là: ~ c \times mex_{x \in V} \{a_x\} + d \times max_{x \in V} \{a_x\} ~

Hãy tìm độ đẹp lớn nhất của tất cả các đường đi đơn.

PS: ~mex~ ~V~ là số nguyên không âm nhỏ nhất không xuất hiện trong tập ~V~, ~max~ ~V~ là số lớn nhất trong tập ~V~.

Input:

• Dòng đầu tiên gồm hai ba số nguyên ~n~ ~(1 \le n \le 10^5, 0 \le c,d \le 10^9)~.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~ ~(0 \le a_i \le n-1)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~u_i~ và ~v_i~ miêu tả cạnh ~(u_i,v_i)~ của cây ~(1 \le u_i,v_i \le n)~.

Output:

• In ra đáp án cần tìm.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~n \le 200~
• Subtask ~2~ (~25\%~ số điểm): ~n \le 2000~
• Subtask ~3~ (~25\%~ số điểm): ~d = 0~
• Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

25

Cho đồ thị đơn vô hướng gồm ~n~ đỉnh và ~m~ cạnh.

Có ~q~ câu hỏi, mỗi câu hỏi bạn nhận được một giá trị ~k~, tìm cách thêm đúng ~k~ cạnh vào đồ thị sao cho số cạnh cầu của đồ thị mới là ít nhất. Lưu ý rằng bắt đầu mỗi truy vấn, chúng ta chỉ xem xét với đồ thị gốc.

Input

• Dòng đầu chứa ba số nguyên ~n,m,q~ ~(1 \le n,q \le 10^5)~ và ~(1 \le m \le 2 \times 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_i, v_i~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i)~.
• ~q~ dòng sau, mỗi dòng gồm một số nguyên ~k~ miêu tả truy vấn.

Output

• Mỗi dòng in ra kết quả tương ứng của truy vấn là số cạnh cầu bị xóa.

Subtask

• Subtask ~1~: ~q = 1~ và đồ thị là cây. ~(20\%)~
• Subtask ~2~: ~q = 1, k = 1, n \le 10^3~. ~(20\%)~
• Subtask ~3~: ~q = 1, k = 1, n \le 10^5~. ~(20\%)~
• Subtask ~4~: ~q = 1~ ~(20\%)~.
• Subtask ~5~: Không có ràng buộc gì thêm ~(20\%)~.

Sample Input 1

3 2 1
1 2
2 3
1

Sample Output 1

2