Công ty Just Odd Inventions, gọi tắt là JOI, chuyên tạo ra những phát minh kỳ lạ. Công ty Incredibly Odd Inventions, gọi tắt là IOI, chuyên tạo ra những phát minh kỳ lạ đến khó tin. IOI luôn đánh cắp thông tin về các dự án nghiên cứu của JOI để tạo ra các phát minh của mình.

Mỗi công ty có \(N\) nhân viên. Nhân viên của JOI được gọi là \(j_1,j_2,\ldots,j_N\), còn nhân viên của IOI là \(i_1,i_2,\ldots,i_N\). Trong mỗi công ty có đúng một nhân viên là giám đốc. Mỗi nhân viên khác có đúng một cấp trên trực tiếp trong cùng công ty.

JOI vừa bắt đầu \(M\) dự án nghiên cứu \(r_1,r_2,\ldots,r_M\), còn IOI bắt đầu \(M\) dự án gián điệp \(s_1,s_2,\ldots,s_M\). Dự án gián điệp \(s_b\) nhằm đánh cắp thông tin của dự án nghiên cứu \(r_b\).

Hai công ty xác định thành viên dự án theo cùng một cách. Mỗi dự án có một trưởng dự án. Trưởng dự án ra lệnh cho tất cả cấp dưới trực tiếp của mình; mỗi người nhận lệnh lại truyền lệnh cho tất cả cấp dưới trực tiếp của họ. Thành viên dự án gồm trưởng dự án và mọi nhân viên nhận được lệnh, không có ai khác.

Nhân viên \(i_a\) chỉ đánh cắp thông tin từ nhân viên \(j_a\). Nếu \(i_a\) thuộc dự án gián điệp \(s_b\) và \(j_a\) thuộc dự án nghiên cứu \(r_b\), thì \(i_a\) thành công trong dự án \(s_b\). Mỗi nhân viên có thể thuộc nhiều dự án, và một nhân viên IOI có thể thành công trong nhiều dự án gián điệp.

Yêu cầu

Cho cơ cấu nhân viên và thông tin các dự án của hai công ty, hãy tính với mỗi nhân viên IOI số dự án gián điệp mà người đó thành công.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,M\). Mỗi công ty có \(N\) nhân viên và \(M\) dự án.
• Trong \(N\) dòng tiếp theo, dòng thứ \(a\) chứa hai số nguyên \(P_a,Q_a\). Nếu \(P_a\ne0\) thì \(j_a\) là cấp dưới trực tiếp của \(j_{P_a}\); nếu \(P_a=0\) thì \(j_a\) là giám đốc JOI. Tương tự, nếu \(Q_a\ne0\) thì \(i_a\) là cấp dưới trực tiếp của \(i_{Q_a}\); nếu \(Q_a=0\) thì \(i_a\) là giám đốc IOI.
• Trong \(M\) dòng tiếp theo, dòng thứ \(b\) chứa hai số nguyên \(R_b,S_b\). Trưởng dự án nghiên cứu \(r_b\) là \(j_{R_b}\), còn trưởng dự án gián điệp \(s_b\) là \(i_{S_b}\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(a\) chứa một số nguyên là số dự án gián điệp mà nhân viên \(i_a\) thành công.

Ràng buộc

• Giới hạn thời gian: 2 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(1\le N\le2000\).
• \(1\le M\le500000\).
• \(0\le P_a,Q_a\le N\).
• \(1\le R_b,S_b\le N\).
• Mỗi công ty có đúng một giám đốc; mỗi nhân viên khác có đúng một cấp trên trực tiếp trong cùng công ty.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (10 điểm): \(N\le200\), \(M\le200\).
• Nhóm 2 (20 điểm): \(M\le2000\).
• Nhóm 3 (70 điểm): Không có ràng buộc bổ sung.

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

1
0
2

Trong JOI, giám đốc là \(j_1\), \(j_2\) là cấp dưới trực tiếp của \(j_1\), và \(j_3\) là cấp dưới trực tiếp của \(j_2\). Trong IOI, giám đốc là \(i_2\), còn \(i_1\) và \(i_3\) đều là cấp dưới trực tiếp của \(i_2\). Các dự án có thành viên như sau:

• Nhân viên \(i_1\) thuộc các dự án \(s_1,s_2,s_4\). Vì \(j_1\) thuộc \(r_1\), người này thành công trong dự án \(s_1\).
• Nhân viên \(i_2\) thuộc dự án \(s_4\). Vì \(j_2\) không thuộc \(r_4\), người này không thành công trong dự án gián điệp nào.
• Nhân viên \(i_3\) thuộc các dự án \(s_3,s_4\). Vì \(j_3\) thuộc cả \(r_3\) lẫn \(r_4\), người này thành công trong cả hai dự án \(s_3,s_4\).