题目描述

有 $N$ 个城市，还有 $K$ 条道路和 $L$ 条铁路，它们在城市之间延伸。第 $i$ 条道路双向连接第 $p_i$ 个和第 $q_i$ 个城市，第 $i$ 条铁路双向连接第 $r_i$ 个和第 $s_i$ 个城市。没有两条道路连接同一对城市。同样地，没有两条铁路连接同一对城市。

如果通过一些道路可以从城市 $A$ 到达城市 $B$，那么我们将称城市 $A$ 和 $B$ 是 由道路相连的 。在这里，任何城市被认为是通过道路与自己相连的。我们也将类似地定义 由铁路相连的连通性 。

对于每个城市，找到通过道路和铁路都与该城市相连的城市的数量。

约束条件

• $2 ≦ N ≦ 2\*10^5$
• $1 ≦ K, L≦ 10^5$
• $1 ≦ p_i, q_i, r_i, s_i ≦ N$
• $p_i < q_i$
• $r_i < s_i$
• 当 $i ≠ j$ 时，$(p_i, q_i) ≠ (p_j, q_j)$
• 当 $i ≠ j$ 时，$(r_i, s_i) ≠ (r_j, s_j)$

输入

输入以以下格式从标准输入给出：

$N$ $K$ $L$ $p_1$ $q_1$ : $p_K$ $q_K$ $r_1$ $s_1$ : $r_L$ $s_L$

输出

输出 $N$ 个整数。其中第 $i$ 个整数表示通过道路和铁路都与第 $i$ 个城市相连的城市的数量。

示例输入 1

4 3 1
1 2
2 3
3 4
2 3

示例输出 1

1 2 2 1

这四个城市互相通过道路相连。

通过铁路，只有第二个和第三个城市是相连的。因此，这些城市的答案分别为 $1, 2, 2$ 和 $1$。

示例输入 2

4 2 2
1 2
2 3
1 4
2 3

示例输出 2

1 2 2 1

示例输入 3

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

示例输出 3

1 1 2 1 2 2 2