D - Melee Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

1 から N の番号がついた N 人のプレイヤーがとある対戦型格闘ゲームで遊びます。 対戦開始時と同時に、N 人のプレイヤーはゲーム上でリングに登場します。対戦開始時の全プレイヤーのスコアは 0 です。

その後、対戦中に M 個のイベントが起きます。各イベントは下記のタイプ 1 またはタイプ 2 のどちらかです。

  • タイプ 1 : 下記の形式で示される。プレイヤー x が、プレイヤー y に攻撃する。
1 x y
  • タイプ 2 : 下記の形式で示される。プレイヤー z がリングから脱落する。
2 z

プレイヤーがリングから脱落すると、直ちに下記の出来事が起きます。

  • 脱落したプレイヤーのスコアが 1 だけ減少する。
  • 脱落したプレイヤーが直前にリングに登場した後に 1 回以上攻撃されていた場合、そのうち最後の攻撃を行ったプレイヤーのスコアが 1 だけ増加する。
  • その後、脱落したプレイヤーはリングに再び登場する。

各プレイヤーの最終的なスコアを出力してください。

制約

  • 入力はすべて整数
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq x, y, z \leq N
  • x \neq y

入力

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

N M
\mathrm{event}_1
\mathrm{event}_2
\vdots
\mathrm{event}_M

i = 1, 2, \ldots, M について、\mathrm{event}_i は i 番目に起きたイベントを表し、 問題文中に示されたタイプ 1 とタイプ 2 のどちらかの形式である。

出力

i = 1, 2, \ldots, N について、プレイヤー i の最終的なスコア S_i を下記の形式で空白区切りで出力せよ。

S_1 S_2 \ldots S_N

入力例 1

4 6
1 2 3
1 4 3
2 3
1 2 1
2 2
2 3

出力例 1

0 -1 -2 1

対戦開始時、4 人のプレイヤーがリングに登場し、各プレイヤーのスコアは (S_1, S_2, S_3, S_4) = (0, 0, 0, 0) です。 その後、対戦中に下記の通りにイベントが起きます。

  • 1 番目のイベントでは、プレイヤー 2 がプレイヤー 3 に攻撃します。
  • 2 番目のイベントでは、プレイヤー 4 がプレイヤー 3 に攻撃します。
  • 3 番目のイベントでは、プレイヤー 3 が脱落します。その結果、プレイヤー 3 のスコアが 1 だけ減少します。また、プレイヤー 3 が直前にリングに登場したとき（すなわち、対戦開始時）より後に、プレイヤー 3 は 1 番目と 2 番目のイベントで攻撃されているため、そのうち最後の攻撃を行ったプレイヤー 4 のスコアが 1 だけ増加します。その後、プレイヤー 3 は再びリングに登場します。
  • 4 番目のイベントでは、プレイヤー 2 がプレイヤー 1 に攻撃します。
  • 5 番目のイベントでは、プレイヤー 2 が脱落します。その結果、プレイヤー 2 のスコアが 1 だけ減少します。プレイヤー 2 が直前にリングに登場したとき（すなわち、対戦開始時）より後に、プレイヤー 2 は 1 回も攻撃されていません。その後、プレイヤー 2 は再びリングに登場します。
  • 6 番目のイベントでは、プレイヤー 3 が脱落します。その結果、プレイヤー 3 のスコアが 1 だけ減少します。プレイヤー 3 が直前にリングに登場したとき（すなわち、3 番目のイベントの最後）より後に、プレイヤー 3 は 1 回も攻撃されていません。その後、プレイヤー 3 は再びリングに登場します。

各プレイヤーの最終的なスコアは　(S_1, S_2, S_3, S_4) = (0, -1, -2, 1) となります。

入力例 2

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

出力例 2

-1 -1 -1 0 0

Problem Statement

N players numbered 1 through N are playing a multiplayer fighting game. When a match starts, the N players enter a ring at once. Initially, each player's score is 0.

Then, M events occur during the match. Each event is of type 1 or type 2 described below:

  • Type 1: represented in the following format. Player x attacks player y.
1 x y
  • Type 2: represented in the following format. Player z drops out of the ring.
2 z

When a player drops out of the ring, the following events immediately occur:

  • The score of the player who has dropped out decreases by 1.
  • If the player who has dropped out was attacked at least once since the last entrance, the score of the player who made the last such attack increases by 1.
  • Then, the player enters the ring again.

Print the final score of each player.

Constraints

  • All input values are integers.
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq x, y, z \leq N
  • x \neq y

Input

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

N M
\mathrm{event}_1
\mathrm{event}_2
\vdots
\mathrm{event}_M

For i = 1, 2, \ldots, M, \mathrm{event}_i represents the i-th event, and is in type-1 or type-2 format described in the problem statement.

Output

For i = 1, 2, \ldots, N, print the final score S_i of player i in the following format, separated by spaces:

S_1 S_2 \ldots S_N

Sample Input 1

4 6
1 2 3
1 4 3
2 3
1 2 1
2 2
2 3

Sample Output 1

0 -1 -2 1

When the match starts, 4 players enter the ring, and the players' scores are (S_1, S_2, S_3, S_4) = (0, 0, 0, 0). Then, the following events occur during the match:

  • In the 1-st event, player 2 attacks player 3.
  • In the 2-nd event, player 4 attacks player 3.
  • In the 3-rd event, player 3 drops out, so their score decreases by 1. Since player 3's last entrance (i.e. since the match begins), they are attacked in the 1-st and 2-nd event. The last one among them is made by player 4, so their score increases by 1. Subsequently, player 3 enters the ring again.
  • In the 4-th event, player 2 attacks player 1.
  • In the 5-th event, player 2 drops out, so their score decreases by 1. Since player 2's last entrance (i.e. since the match begins), they are never attacked. Subsequently, player 2 enters the ring again.
  • In the 6-th event, player 3 drops out, so their score decreases by 1. Since player 3's last entrance (i.e. since the 3-rd event), they are never attacked. Subsequently, player 3 enters the ring again.

The final scores of the players are (S_1, S_2, S_3, S_4) = (0, -1, -2, 1).

Sample Input 2

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

Sample Output 2

-1 -1 -1 0 0