分数: 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