← 返回题目列表

AtCoder · arc065_b

D. 连接性

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N 城市。还有 K 道路和 L 铁路,在城市之间延伸。 的 i第条路双向连接 p_i-th 和 q_i第 个城市,以及 i第铁路双向连接 r_i-th 和 s_i第个城市。 没有两条道路连接同一对城市。同样,没有两条铁路连接同一对城市。

我们会说城市 A 和 B 是 有道路相连 如果城市 从城市可到达 B 从城市可到达 A 穿过一些道路。在这里,任何城市都被认为是通过道路与其自身相连的。 我们还将定义 铁路互联互通 类似。

对于每个城市,查找通过公路和铁路连接到该城市的城市数量。

约束

  • 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