H - バス路線 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

左右一列に N 個のバス停が並んでいます。バス停は左から 1,2,\ldots,N と番号が付けられています。

M 本のバス路線があります。i 番目 (1 \leq i \leq M) のバス路線はバス停 L_i からバス停 R_i までを往復するバス路線で、バス停 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 番目のバス路線はバス停 2,3,4,5 に、 3 番目のバス路線はバス停 1,2,3,4 に、 4 番目のバス路線はバス停 2,3 に、 5 番目のバス路線はバス停 4,5 に停まります。

つまり、バス停 1 に停まる路線は 1,3 番目の路線、バス停 2 に停まる路線は 1,2,3,4 番目の路線、バス停 3 に停まる路線は 1,2,3,4 番目の路線、バス停 4 に停まる路線は 2,3,5 番目の路線、バス停 5 に停まる路線は 2,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

Problem Statement

N bus stops are arranged from left to right, numbered 1,2,\ldots,N in order.

There are M bus routes. Route i (1 \leq i \leq M) operates bidirectionally between bus stops L_i and R_i, stopping at every bus stop in between, including these two.

Find how many routes stop at each bus stop.

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

Print N lines. The i-th line should contain the number of routes that stop at bus stop i.

Sample Input 1

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

Sample Output 1

2 4 4 3 2

Route 1 stops at bus stops 1,2,3; route 2 at 2,3,4,5; route 3 at 1,2,3,4; route 4 at 2,3; and route 5 at 4,5.

In other words, routes 1 and 3 stop at bus stop 1; routes 1,2,3,4 stop at 2; routes 1,2,3,4 stop at 3; route 2,3,5 stop at 4; and routes 2,5 stop at 5.

Thus, the numbers to be printed are 2,4,4,3,2, in order.

Sample Input 2

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

Sample Output 2

2 5 4 4 4 4 6 4 2 0