D - Card Pile Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

カードが N 枚とカードの山が N 個あります。

カードとカードの山にはそれぞれ 1, 2, \ldots, N の番号が付けられており、はじめ、山 i にはカード i のみが積まれています。

あなたは、各 i = 1, 2, \ldots, Q に対して以下の操作をこの順に行います。

  • カード C_i およびカード C_i の上に積まれているカードを順序を保ってカード P_i の上に移動させる。ただし、操作を行う直前の時点でカード C_i とカード P_i は異なる山にあり、カード P_i はある山の一番上に積まれていることが保証される。

すべての操作を終えた後、各山に積まれているカードの枚数を求めてください。

制約

  • 1 \leq N, Q \leq 3 \times 10^5
  • 1 \leq C_i, P_i \leq N
  • 操作を順に行ったとき、各操作を行う直前の時点でカード C_i とカード P_i は異なる山にある
  • 操作を順に行ったとき、各操作を行う直前の時点でカード P_i はある山の一番上に積まれている
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
C_1 P_1
C_2 P_2
\vdots
C_Q P_Q

出力

最終的に山 i に積まれているカードの枚数を A_i として A_1, A_2, \ldots, A_N をこの順に空白区切りで出力せよ。

入力例 1

5 4
1 3
4 5
1 4
4 2

出力例 1

0 3 1 0 1

一連の操作は以下の図のように行われます。

入力例 2

7 8
3 1
5 4
2 5
5 7
2 3
6 2
3 4
5 1

出力例 2

2 0 0 4 0 0 1

Score : 400 points

Problem Statement

There are N cards and N piles of cards.

The cards and the piles are numbered 1, 2, \ldots, N. Initially, pile i contains only card i.

Perform the following operation for each i = 1, 2, \ldots, Q in order:

  • Move card C_i and all cards stacked on top of card C_i, preserving their order, on top of card P_i. It is guaranteed that immediately before performing the operation, cards C_i and P_i are in different piles, and card P_i is on top of some pile.

Find the number of cards in each pile after all operations are completed.

Constraints

  • 1 \leq N, Q \leq 3 \times 10^5
  • 1 \leq C_i, P_i \leq N
  • When the operations are performed in order, immediately before each operation, cards C_i and P_i are in different piles.
  • When the operations are performed in order, immediately before each operation, card P_i is on top of some pile.
  • All input values are integers.

Input

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

N Q
C_1 P_1
C_2 P_2
\vdots
C_Q P_Q

Output

Let A_i be the number of cards in pile i at the end. Output A_1, A_2, \ldots, A_N in this order, separated by spaces.

Sample Input 1

5 4
1 3
4 5
1 4
4 2

Sample Output 1

0 3 1 0 1

The sequence of operations proceeds as shown in the figure below.

Sample Input 2

7 8
3 1
5 4
2 5
5 7
2 3
6 2
3 4
5 1

Sample Output 2

2 0 0 4 0 0 1