Đất nước Free Contest gồm ~N~ thành phố. Có ~M~ tuyến đường bộ và ~L~ tuyến đường sắt, các tuyến đường đều là đường hai chiều. Tuyến đường bộ thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~, tuyến đường sắt thứ ~i~ nối hai thành phố ~x_i~ và ~y_i~. Không có hai tuyến đường bộ nào nối cùng một cặp thành phố. Tương tự, không có hai tuyến đường sắt nào nối cùng một cặp thành phố.

Hai thành phố ~s~ và ~t~ được gọi là liên thông bằng đường bộ nếu có thể đi từ ~s~ đến ~t~ chỉ bằng các tuyến đường bộ. Tương tự, hai thành phố ~s~ và ~t~ được gọi là liên thông bằng đường sắt nếu có thể đi từ ~s~ đến ~t~ chỉ bằng các tuyến đường sắt.

Với mỗi thành phố ~u~, hãy cho biết có bao nhiêu thành phố ~v~ sao cho:

• ~u~ và ~v~ liên thông bằng đường bộ
• ~u~ và ~v~ liên thông bằng đường sắt

Theo định nghĩa trên, mỗi thành phố đều liên thông bằng đường bộ và liên thông bằng đường sắt với chính nó.

Dữ liệu

• Dòng đầu tiên ghi một số nguyên dương ~N,M,L\ (N,M,L ≤ 200000)~ - số thành phố, số tuyến đường bộ và số tuyến đường sắt
• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~u_i~ và ~v_i\ (u_i < v_i)~ - tuyến đường bộ thứ ~i~.
• ~L~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~x_i~ và ~y_i~ ~(x_i < y_i)~ - tuyến đường sắt thứ ~i~.

Kết quả

• In ra ~N~ số nguyên, số nguyên thứ ~i~ là số thành phố liên thông bằng đường bộ và liên thông bằng đường sắt với thành phố thứ ~i~.

Chấm điểm

• Subtask 1 (30% số điểm): ~N,M,L ≤2000~
• Subtask 2 (70% số điểm): Không có ràng buộc gì thêm

Ví dụ

Sample Input 1

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

Sample Output 1

1 3 3 3

Sample Input 2

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

Sample Output 2

2 2 2 2 1 1 1

Giải thích

• Hình vẽ minh họa ví dụ thứ nhất (đường nét liền tương ứng với đường bộ, đường nét đứt tương ứng với đường sắt). Với thành phố ~3~ thì các thành phố cần đếm là ~2, 3, 4~.
• Hình vẽ minh họa ví dụ thứ hai

Nguồn: Free Contest