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ác đỉnh được đánh số từ 1 đến n. Đỉnh 1 là gốc của cây. Đỉnh thứ i được tô màu ~c_i~. Bạn cần trả lời ~q~ câu hỏi. Tại câu hỏi thứ j, bạn được cho một đỉnh ~v_j~ trên cây và một số ~k_j~; bạn cần cho biết có bao nhiêu màu mà trong cây con gốc ~v_j~ có ít nhất ~k_j~ đỉnh chứa màu đó.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ là số đỉnh của cây (~1 \le n \le 3 * 10^5~).
• Dòng thứ hai chứa n số nguyên ~c_1, c_2, ..., c_n~ (~1 ≤ c_i ≤ n~) lần lượt là màu được tô ở các đỉnh trên cây.
• Trong ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ (~1 ≤ u, v ≤ n~) cho biết trên cây có một cạnh nối hai đỉnh u và v.
• Dòng tiếp theo chứa số nguyên ~q~ (~1 ≤ q ≤ 5*10^5~) là số câu hỏi bạn cần trả lời.
• Trong q dòng cuối cùng, dòng thứ j chứa hai số nguyên ~v_j~ và ~k_j~ (~1 ≤ v_j, k_j ≤ n~) thể hiện câu hỏi thứ i.

Output

• In ra q số nguyên lần lượt là câu trả lời cho q câu hỏi.

Subtask

• 25% ~n,q \le 3000~
• 25% ~n \le 5000~
• 10% ~c_i \le 50~
• 15% ~c_i = i~
• 25% không giới hạn gì thêm

Example

Sample Input

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

Sample Output

3 2 1 0 3 3 3 0 

Note

• Trong ví dụ trên, các đỉnh thuộc cây con gốc 2 bao gồm 2, 4, 5, 6, 7 và 9; trong đó có 1 đỉnh được tô màu 1, 2 đỉnh được tô màu 3 và 3 đỉnh được tô màu 2. Như vậy, trong cây con gốc 2 có 3 màu với ít nhất 1 đỉnh, 2 màu với ít nhất 2 đỉnh và 1 màu với ít nhất 3 đỉnh.

Cây là một đồ thị vô hướng liên thông và không có chu trình. Một cây có ~n~ đỉnh luôn luôn có đúng ~n - 1~ cạnh. Giữa hai đỉnh bất kì của cây, có một và chỉ một đường đi đơn duy nhất. Đường đi đơn là đường đi chỉ đi qua mỗi đỉnh và mỗi cạnh không quá một lần.

Một thành phần liên thông trong đồ thị vô hướng là một tập hợp ~S~ các đỉnh của đồ thị thỏa mãn các tính chất sau đây:

• Với mọi cặp đỉnh ~x~ và ~y~ sao cho nếu ~{x, y}~ thuộc ~S~, tồn tại một đường đi từ x đến y chỉ đi qua các đỉnh thuộc ~S~.
• Tập hợp ~S~ là cực đại, nói cách khác, không thể thêm một đỉnh nào vào tập ~S~ sao cho tính chất trên vẫn còn đúng.
• Trong một cây, nếu ta chọn một đỉnh ~u~ và xóa đỉnh này cùng các cạnh liên thuộc khỏi cây, ta có thể được một đồ thị với một hoặc nhiều thành phần liên thông. Cho một cây gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~n~. Mỗi đỉnh được tô một màu. Hãy tìm cách xóa một đỉnh của cây và các cạnh liên thuộc với đỉnh này, sao cho mọi thành phần liên thông tạo thành sao khi xóa chỉ chứa các đỉnh cùng màu.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ là số đỉnh của cây (~1 \le n \le 1 * 10^6~).
• 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.
• Dòng cuối cùng chứa n số nguyên ~c_1, c_2, ..., c_n~ ~(1 ≤ c_i ≤ 10^6)~ thể hiện màu của các đỉnh trên cây. Đỉnh i và đỉnh j được tô cùng màu khi và chỉ khi ~c_i = c_j~.

Output

• Dòng đầu tiên in ra từ YES nếu tồn tại một cách xóa đi một đỉnh sao cho sau khi xóa, mọi cặp đỉnh thuộc cùng thành phần liên thông luôn cùng màu, in ra NO nếu ngược lại. Nếu dòng đầu tiên in ra YES, dòng thứ hai in ra một dãy số nguyên là chỉ số của các đỉnh có thể xóa. Các chỉ số cần được sắp xếp theo thứ tự tăng dần.

Subtask

• 25% ~n \le 500~
• 25% ~n \le 3000~
• 25% đồ thị dạng đường thẳng
• 25% không giới hạn gì thêm

Example

Sample Input 1

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

Sample Output 1

YES
4 

Sample Input 2

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

Sample Output 2

NO 

Sample Input 3

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

Sample Output 3

YES
1 2 3 4 5 6 7 

Note

• Đồ thị sau khi xóa đi đỉnh 4 (và các cạnh kề với 4) có 4 thành phần liên thông: {1} chỉ chứa các đỉnh màu đỏ, {2} chỉ chứa các đỉnh màu đỏ, {5, 6} chỉ chứa các đỉnh màu xanh lá cây, {3, 7} chỉ chứa các đỉnh màu tím.
• Trong ví dụ thứ hai, mỗi đỉnh của cây có một màu khác nhau, nên không tồn tại cách xóa đỉnh thỏa mãn các điều kiện của đề bài.
• Trong ví dụ thứ ba, tất cả các đỉnh có cùng màu. Do đó dù xóa đi đỉnh nào, đồ thị sau khi xóa cũng gồm các thành phần liên thông với các đỉnh cùng màu.

Siêu thị BigC hôm nay bán ~n~ món ăn, món ăn thứ ~i~ có giá là ~c_i~ đồng. Khách hàng chỉ được mua mỗi món ăn tối đa một lần. Do là học sinh giàu vượt sướng, Walter chỉ muốn tiêu tối đa ~b~ đồng.

Hôm nay siêu thị bigC đưa ra một chương trình khuyến mãi hấp dẫn: Với món ăn thứ ~i~, thay vì mua với giá ~c_i~ ban đầu, khách mua có thể trả ít hơn ~d_i~ đồng. Tuy nhiên, chương trình này đi kèm ràng buộc: Với mỗi món ăn ~i > 1~, có một món ăn ~p_i < i~ mà nếu khách hàng muốn mua món ăn ~i~ với giá ưu đãi, họ bắt buộc phải mua món ăn ~p_i~ cũng với giá ưu đãi. Hệ quả là, họ có thể cũng phải mua tiếp món ăn ~p_{p_i}~ cũng với giá ưu đãi...

Hãy giúp Walter tìm ra số món ăn tối đa có thể mua mà không vượt quá hạn mức chi tiêu đã đề ra

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~b~ là số món ăn được bán tại siêu thị BigC và hạn mức chi tiêu của Walter (~1 \le n \le 5 * 10^3~, ~1 \le b \le 10^9~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~c_i~ và ~d_i~ (~1 ≤ d_i < c_i ≤ 10^9~) — mức giá ban đầu của món ăn thứ ~i~ và số tiền được giảm nếu mua món ăn thứ ~i~ với giá ưu đãi. Nếu ~i > 1~, dòng này sẽ có thêm số nguyên ~p_i~ (~1 ≤ p_i ≤ i - 1~) cho biết món ăn cần được mua với giá ưu đãi nếu chọn mua món ăn thứ ~i~ cũng với giá ưu đãi.

Output

• Gồm một dòng duy nhất là số món ăn nhiều nhất mà Walter có thể mua với b đồng

Subtask

• 25% ~n \le 20~
• 30% ~n,b \le 300~
• 45% không giới hạn gì thêm

Example

Sample Input

6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5

Sample Output

4

Note

Trong ví dụ trên cách mua tối ưu là:

• Mua món ăn số 1 với giá ưu đãi 10 - 9 = 1 đồng.
• Mua món ăn số 3 với giá ưu đãi 12 - 2 = 10 đồng.
• Mua món ăn số 4 với giá ưu đãi 20 - 18 = 2 đồng.
• Mua món ăn số 6 với giá ban đầu 2 đồng.

Tồng số tiền cần tiêu là 1 + 10 + 2 + 2 = 15 đồng, nằm trong hạn mức 16 đồng đã đề ra.