[ABC049D] 連結
题意翻译
## 题目描述
有$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$个正整数,表示每个点只通过道路和只通过地铁都能到达的点的个数。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc049/tasks/arc065_b
$ 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 $ 番目の都市と道路・鉄道の両方で連結している都市の数である。
输入输出样例
输入样例 #1
4 3 1
1 2
2 3
3 4
2 3
输出样例 #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
说明
### 制約
- $ 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 $ となります。