Cây - được định nghĩa là một đồ thị vô hướng liên thông gồm n đỉnh và không có chu trình. Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, nếu đó là một cây thì in ra "Yes", ngược lại in ra "No".

Input:

• Dòng đầu gồm 2 số ~n~ và ~m~. ~(2 \le n, m \le 1e5).~
• ~m~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u, v \le n)~ chỉ ra tồn tại một cạnh vô hướng giữa 2 đỉnh này.

Output:

• Nếu đồ thị đã cho là một cây, in ra "Yes", ngược lại in ra "No".

Sample Test 1

Input:

3 2
1 2
2 3

Output:

Yes

Sample Test 2

Input:

3 3 
1 2 
2 3 
3 1

Output:

No

Cho một cây vô hướng gồm ~n~ đỉnh, có gốc là đỉnh ~1~. Đỉnh ~i~ gồm một số ~a[i]~, nếu ~a[i] = 1~, nghĩa là có một chú mèo ở đỉnh ~i~, còn ngược lại thì không. Thinkies đang ở đỉnh ~1~, cậu chỉ có thể đi tới các đỉnh khác khi và chỉ khi từ đỉnh ~1~ tới đỉnh đó có số mèo trên các đỉnh liên tiếp nhỏ hơn hoặc bằng ~m~. Hãy đếm số đỉnh lá (các đỉnh không có đỉnh con) mà Thinkies có thể đi vào.

Input:

Dòng đầu gồm ~2~ số nguyên ~n~ và ~m~ (~1 \leq m \leq n \leq 10^5~).

Dòng sau gồm ~n~ số biểu thị dãy ~a~.

~n - 1~ dòng kế tiếp, mỗi dòng gồm 2 số ~u~ và ~v~, biểu thị có cạnh giữa 2 đỉnh ~u~ và ~v~.

Output:

In ra số lá mà Thinkies có thể đi vào

Mẫu:

Input:

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

Output:

2

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

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 vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

• Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
• ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
• Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.

Output:

• Số đỉnh tốt.

Sample Test

Input:

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

Output:

3

Giải thích:

• 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

• Subtask 1: ~n <= 500.~ (50%)
• Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
• Subtask 3: Không giới hạn gì thêm. (20%).

Ở một đất nước nọ, có ~n~ thành phố được kết nối với nhau bằng ~n-1~ con đường 2 chiều, đảm bảo rằng từ một thành phố bất kì có thể tới được tất cả các thành phố khác.

Thành phố thứ ~i~ có một giá trị ~a_i~, là độ "đẹp của thành phố đó. Các giá trị a_i này có thể giống nhau, tức là các thành phố có thể có độ đẹp ngang nhau.

Một vị khách du lịch khi tới đất nước này chơi trong ~k (1 \le k \le 10^{18})~ ngày. Hiện tại, vị khách ấy đang ở thành phố 1. Cách di chuyển của vị khách này rất đặc biệt, ví dụ ở ngày thứ i và vị khách đang ở thành phố ~u~ (ở ngày đầu thì anh ta ở thành phố 1), anh sẽ đi tới thành phố ~v~ khác ~u~, sao cho ~a_v - dist(u,v)~ là lớn nhất (~dist(u,v)~ là đường đi ngắn nhất từ thành phố ~u~ tới ~v~). Nếu có nhiều thành phố thỏa mãn điều kiện trên, anh ta sẽ đi tới thành phố có chỉ số nhỏ nhất.

Là một người yêu thích tin học, vị khách đưa ra một yêu cầu trước khi tham quan, đó là hãy tính xem, sau ~k~ ngày, anh ta sẽ ở thành phố nào. Hãy lập trình và giải bài toán này giúp anh ấy.

Input

• Dòng đầu gồm 2 số ~n~ và ~k~, lần lượt là số thành phố và số ngày vị khách ở ~(1 \le n \le 3 \times 10^5, 1 \le k \le 10^{18})~.
• Dòng sau gồm ~n~ số miêu tả dãy ~a~. ~(0 \le a_i \le 10^9 \; \forall \; 1 \le i \le n).~
• ~n-1~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ miêu tả con đường 2 chiều nối ~u~ và ~v~.

Output

In ra thành phố mà anh ta sẽ đến sau ~k~ ngày.

Ràng buộc

• Subtask 1: ~n \le 1000, k \le 10^5~ (20%)
• Subtask 2: ~n \le 1000, k \le 10^{18}~ (15%)
• Subtask 3: ~n \le 300000, k \le 10^5~ (50%)
• Subtask 4: ~n \le 300000, k \le 10^{18}~ (15%)

Sample Test

Input:

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

Output:

5

Giải thích:

• Vị khách sẽ đi theo thứ tự 1 --> 3 --> 5 --> 2 --> 5