问题陈述
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