Koi đi tham quan ở một khu du lịch nọ, cậu thấy một cây sáng rất rực rỡ. Các điểm rẽ trên cây (bao gồm cả gốc, lá cây) có tổng cộng $9$ màu khác nhau. Người quản lý cho cậu biết rằng đây là một "cây đa sắc", đồng thời chỉ rõ cho cậu cấu trúc cây: gốc cây được đánh dấu số $1$, các điểm rẽ còn lại được đánh dấu các số tự nhiên liên tiếp từ $2$ trở đi. Ông đố Koi một câu hỏi như sau: từ một điểm rẽ $u$ trên cây, đếm nhanh số lượng điểm rẽ con, bao gồm cả điểm rẽ gốc có màu $c$ với $u$ và $c$ cho trước.

Các bạn hãy lập trình giúp Koi giải đáp câu hỏi này trong thời gian nhanh nhất nhé.

Ghi chú: Một cây có $V$ điểm thì có đúng $V-1$ cành.

Đầu vào

Dòng đầu tiên gồm hai số tự nhiên $V,Q$ $(1\le V,Q\le {10}^5)$ lần lượt là số điểm rẽ trên cây và số truy vấn.

$V-1$ dòng tiếp theo mỗi dòng chứa hai số tự nhiên $u,v$ $(1\le u,v\le V)$ với ý nghĩa có cành nối điểm $u$ và điểm $v$.

Dòng tiếp theo gồm $V$ số tự nhiên $c$ $(1\le c\le 9)$ với ý nghĩa: số tự nhiên thứ $i$ là màu của điểm $i$.

$Q$ dòng tiếp theo mỗi dòng chứa hai số tự nhiên $u,c$ $(1\le u\le V,1\le c\le 9)$ là truy vấn đếm số điểm con từ $u$ có màu $c$.

Dữ liệu nhập vào đảm bảo tạo thành một cây.

Đầu ra

$Q$ dòng, mỗi dòng gồm duy nhất một số tự nhiên là trả lời của các truy vấn.

Ví dụ

Đầu vào

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

Đầu ra

2
1

Giải thích: Điểm $1,2,3,4$ lần lượt được tô màu $1,1,2,3$; như vậy từ gốc (điểm $1$) có $2$ điểm trên cây có màu $1$ là điểm $1$ và $2$, từ điểm $2$ chỉ có $1$ điểm có màu $1$ là chính nó.