ppp (EGOI contest)
Time limit: 3 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: graph theory, data structures, dfs, tree, segment tree, graph traversal

# Padel Prize Pursuit

![](_page_0_Figure_0.jpeg)

| Problem Name | Padel Prize Pursuit |
|---|---|
| Time Limit | 3 seconds |
| Memory Limit | 1 gigabyte |

There are $N$ participants numbered from 0 to $N - 1$ competing in a padel tournament held over $M$ days. Exactly one match is held each day. There are $M$ medals handed out in the tournament, a new one for each match. In the match on day $i$ ($0 \le i \le M - 1$), the two participants numbered $x_i$ and $y_i$ are participating. The following happens in the match:

*   Participant $x_i$ beats participant $y_i$.
*   A new medal is given to the winner $x_i$.
*   All of the loser's current medals are given to the winner.

On day $M$ (the day after the last match), the prize ceremony is held. At the ceremony, all medals are collected and then each medal is given to the participant that held that medal the longest. Formally, medal $i$ is given to the participant who held medal $i$ for the most nights (not necessarily in a row), as of day $M$. If two or more participants have held a medal for the same number of nights, the medal is given to the participant with the smallest index among them.

Your goal is to determine how many medals each participant is awarded at the prize ceremony.

## Input

The first line of input contains the integers $N$ and $M$, the number of participants and the number of matches.

Then $M$ lines follow. The $i$-th of these lines contains two integers $x_i$ and $y_i$, the participants competing on day $i$, where participant $x_i$ beats participant $y_i$.

## Output

On the single line of output, print $N$ integers, the $k$-th number representing the number of medals that participant $k$ has after the prize ceremony.

## Constraints and Scoring

*   $2 \le N \le 200\,000$.
*   $1 \le M \le 200\,000$.
*   $0 \le x_i, y_i \le N - 1$ and $x_i \ne y_i$ (for all $0 \le i \le M - 1$).

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.

| Group | Score | Limits |
|---|---|---|
| 1 | 12 | $N = 2$ |
| 2 | 16 | $N, M \le 2000$ |
| 3 | 15 | The winner of the $i$-th match participates in the $(i + 1)$-th match, for every $i$ such that $0 \le i \le M - 2$. |
| 4 | 20 | At the time of the $i$-th match, $x_i$ has at least as many medals as $y_i$, for every $i$ such that $0 \le i \le M - 1$. |
| 5 | 22 | Once a participant loses, they are never in a match again. |
| 6 | 15 | No additional constraints |

## Example

For the first sample test case, the following illustration shows who held which medals throughout the tournament. When participant 1 loses on the 3rd day, all her medals are given to participant 2.

![](_page_1_Figure_7.jpeg)

The second sample can be seen below.

![](_page_2_Figure_0.jpeg)

After the prize ceremony, participant 0 is given medals 5 and 6, participant 1 is given medals 3 and 4, and participant 2 is given medals 0, 1 and 2.

| Input | Output |
|---|---|
| 3 4\n0 1\n2 1\n1 0\n2 1 | 1 1 2 |
| 3 7\n0 1\n0 2\n2 0\n0 1\n1 0\n2 0\n0 2 | 2 2 3 |
| 6 10\n2 5\n3 0\n4 2\n0 1\n4 3\n2 4\n0 3\n0 2\n5 2\n5 0 | 5 0 1 1 1 2 |

Starter code:

Grader code:

Setup script:

Evaluation script: