题目描述

$N$ 個の都市があり、$K$ 本の道路と $L$ 本の鉄道が都市の間に伸びています。 $i$ 番目の道路は $p_i$ 番目と $q_i$ 番目の都市を双方向に結び、 $i$ 番目の鉄道は $r_i$ 番目と $s_i$ 番目の都市を双方向に結びます。 異なる道路が同じ $2$ つの都市を結ぶことはありません。同様に、異なる鉄道が同じ $2$ つの都市を結ぶことはありません。

ある都市から別の都市に何本かの道路を通って到達できるとき、それらの都市は道路で連結しているとします。また、すべての都市はそれ自身と道路で連結しているとみなします。
鉄道についても同様に定めます。

全ての都市について、その都市と道路・鉄道のどちらでも連結している都市の数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$N$ 個の整数を出力せよ。$i$ 番目の数は $i$ 番目の都市と道路・鉄道の両方で連結している都市の数である。

题目大意

题目描述

有$N$个城市，$K$条道路（指地面上的道路）和$L$条地铁。道路和地铁都是无向的。对于每个点，请你求出它只通过道路和只通过地铁都能到达的点的个数。道路和地铁之间不能换乘，你只能完全通过地铁到达某个点，或者完全通过道路到达某个点。

输入格式

第一行三个正整数$N,K,L$ ($N\le2\times 10^5,K,L\le10^5$)
然后$K$行，每行两个数$p,q$，表示城市$p$和城市$q$通过道路连接。
然后$L$行，每行两个数$r,s$，表示城市$r$和城市$s$通过地铁连接。

输出格式

一行$N$个正整数，表示每个点只通过道路和只通过地铁都能到达的点的个数。

4 3 1
1 2
2 3
3 4
2 3

1 2 2 1

4 2 2
1 2
2 3
1 4
2 3

1 2 2 1

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

1 1 2 1 2 2 2

提示

制約

• $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)$

Sample Explanation 1

$1,\ 2,\ 3,\ 4$ 番目の都市は全て互いに道路で連結しています。 鉄道で連結している都市は $2,\ 3$ のみなので、答えは順に $1,\ 2,\ 2,\ 1$ となります。