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ó.