Codeforces nổi tiếng là một nền tảng lập trình uy tín, nhưng có tin đồn rằng ý tưởng của nhiều bài trên nền tảng này được lấy cảm hứng từ một nền tảng nhỏ hơn, tên là CDOJ.

CDOJ tuy ít phổ biến hơn nhưng cũng có đội ngũ lập trình viên hùng hậu không thua gì Codeforces, với cùng số lượng nhân viên là n người. Mỗi nhân viên trên cả hai nền tảng đều có một cấp trên trực tiếp, ngoại trừ một người duy nhất giữ chức vụ giám đốc là cô Taro ở CD và BenQ ở CF.

Ngoài ra, Codeforces và CDOJ đều có M contest đang triển khai. Với mỗi contest của CDOJ, Codeforces cũng có một contest tương ứng được thực hiện nhằm mục đích "tham khảo" từ các contest Hackdream siêu chất lượng của CDOJ.

Nhiệm vụ của bạn là xác định số lượng contest của CDOJ mà mỗi nhân viên Codeforces đã "tham khảo" thành công.

Yêu cầu

• Nhập số lượng nhân viên n và số lượng contest M.
• Mô tả quan hệ cấp trên của từng nhân viên trong CDOJ và Codeforces.
• Cho biết người phụ trách của từng contest trên cả hai nền tảng.

Đầu ra

• Đối với mỗi nhân viên của CDOJ, hãy in ra số lượng contest mà họ đã "tham khảo" thành công từ các contest của Codeforces.

Ràng buộc

• n ~<= 2e3 ~
• M ~<= 5e3~

Dữ liệu vào

• Dòng đầu tiên gồm 2 số nguyên n và M - số nhân viên và số contest của Codeforces và CDOJ.
• n dòng tiếp theo, dòng thứ a (1 ≤ a ≤ n) gồm 2 số Pa và Qa:
  • Nếu Pa = 0, thì nhân viên ja là giám đốc của CDOJ, nếu không ja là cấp dưới trực tiếp của jPa.
  • Nếu Qa = 0, thì nhân viên ia là giám đốc của CF, nếu không ia là cấp dưới trực tiếp của iQa.
• M dòng tiếp theo, dòng thứ b (1 ≤ b ≤ M) gồm 2 số Rb và Sb:
  • Rb là lãnh đạo của contest rb tại CDOJ.
  • Sb là lãnh đạo của contest sb tại CF.

Kết quả ra

• In ra n dòng, dòng thứ a (1 ≤ a ≤ n) in số contest mà nhân viên ia tại CF đã "tham khảo" thành công từ các contest của CDOJ.

Input

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

Output

1
0
2

Giải thích

Với cấu trúc nhân viên như trong ví dụ, contest "tham khảo" thành công được tính như sau:

• Nhân viên i1 thuộc các contest s1, s2, s4 của Codeforces. Contest s1 thành công vì j1 thuộc contest r1 của CDOJ.
• Nhân viên i2 chỉ tham gia contest s4 của Codeforcesvà không "tham khảo" thành công contest nào từ CDOJ.
• Nhân viên i3 thuộc các contest s3, s4 và thành công ở cả r3 và r4 từ CDOJ.