← 返回题目列表

AtCoder · past22_h

H. 公交线路

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

问题陈述

N 公交车站从左到右排列,编号 1,2,\ldots,N 按顺序。

有 M 巴士路线。 路线 i (1 \leq i \leq M) 在公交车站之间双向运营 L_i 和 R_i,在其间的每个公交车站停靠,包括这两个。

查找每个公交车站有多少条路线停靠。

约束

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq M \leq 3 \times 10^5
  • 1 \leq L_i,R_i \leq N (1 \leq i \leq M)
  • L_i \neq R_i (1 \leq i \leq M)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

打印 N 行。 的 i- 第行应包含在公交车站停靠的路线数 i.


示例输入 1

5 5
1 3
5 2
4 1
2 3
4 5

示例输出 1

2 4 4 3 2

路线 1 在公交车站停靠 1,2,3;路线 2 at 2,3,4,5;路线 3 at 1,2,3,4;路线 4 at 2,3;和路线 5 at 4,5.

换句话说,路线 1 和 3 停在公交车站 1;路线 1,2,3,4 停止于 2;路线 1,2,3,4 停止于 3;路线 2,3,5 停止于 4;和路线 2,5 停止于 5.

因此,要打印的数字是 2,4,4,3,2,按顺序。


示例输入 2

10 10
2 5
6 5
2 1
7 9
7 2
2 4
7 6
8 7
7 9
8 1

示例输出 2

2 5 4 4 4 4 6 4 2 0