Cho ~n~ thành phố được kết nối với nhau bởi ~k~ con đường bộ và ~l~ con đường sắt. Con đường bộ thứ ~i~ hai chiều nối giữa thành phố thứ ~p_i~ và thành phố thứ ~q_i~, tương tự con đường sắt thứ ~i~ hai chiều nối giữa thành phố ~r_i~ và ~s_i~.

Hai thành phố ~A~ và ~B~ được gọi là liên thông theo đường bộ nếu có đường đi bộ giữa chúng, giả thiết thêm là mỗi thành phố là liên thông đến chính nó bằng đường bộ.

Hoàn toàn tương tự cho định nghĩa liên thông bằng đường sắt.

Với mỗi thành phố hãy lập trình chỉ ra số thành phố liên thông với nó bằng cả đường sắt lẫn đường bộ.

Input

Dòng đầu tiên chứa ba số nguyên ~n, k, l~ thỏa ~2 \le n \le 2.10^5; 1 \le k, l \le 10^5~.

~k~ dòng tiếp theo chứa bộ ~p_i, q_i~ là cạnh nối đường bộ giữa hai thành phố thỏa ~p_i < q_i~ khi ~i \neq j, (p_i, q_i) \neq (p_j, q_j); 1 \le p_i, q_i \le n~.

~l~ dòng tiếp theo chứa bộ ~r_i, s_i~ là cạnh nối đường sắt giữa hai thành phố thỏa ~r_i < s_i~ khi ~i \neq j, (r_i, s_i) \neq (r_j, s_j); 1 \le r_i, s_i \le n~.

Output

In ra ~n~ số nguyên, số thứ ~i~ đại diện cho số lượng các thành phố kết nối với thành phố thứ ~i~ bằng cả đường bộ và đường sắt.

Samples

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1