패들 상금 경쟁

시간 제한3초메모리 제한1024 MB

요약

M번의 경기에서 승자는 새 메달을 얻고 패자의 메달을 모두 가져갑니다. 각 메달을 가장 오래 보유한 사람에게 준 뒤 참가자별 메달 수를 구합니다.

난이도: 보통10점 중 7점
유형: 유니온 파인드, 배열, 구현
정답자: 아직 제출이 없습니다

문제

$N$ 명의 참가자가 0번부터 $N-1$ 번까지 번호를 달고 $M$ 일 동안 패들 토너먼트를 치릅니다. 매일 정확히 한 경기가 열립니다. 경기마다 메달이 하나씩 주어지므로 메달은 모두 $M$ 개입니다. $i$ 일차 $(0 \le i \le M-1)$ 경기에서는 참가자 $x_i$ 와 $y_i$ 가 맞붙습니다. 경기는 다음과 같이 진행됩니다.

참가자 $x_i$ 가 $y_i$ 를 이깁니다.
승자 $x_i$ 에게 새 메달이 하나 주어집니다.
패자가 가진 메달은 전부 승자에게 넘어갑니다.

마지막 경기 다음 날인 $M$ 일째에 시상식이 열립니다. 시상식에서는 모든 메달을 회수합니다. 그다음 각 메달을 $M$ 일째 기준으로 그 메달을 가장 오래 보유한 참가자에게 줍니다. 보유한 밤은 연속일 필요가 없습니다. 보유 기간이 같은 참가자가 둘 이상이면 번호가 가장 작은 참가자에게 줍니다. 시상식에서 각 참가자가 받는 메달 개수를 구하세요.

입력

첫 줄에 참가자 수 $N$ 과 경기 수 $M$ 이 정수로 주어집니다.

이어서 $M$ 개의 줄에 각각 정수 $x_i$ 와 $y_i$ 가 주어집니다. $i$ 번째 줄은 $i$ 일차 경기의 참가자이며, $x_i$ 가 $y_i$ 를 이긴 경기입니다.

출력

한 줄에 정수 $N$ 개를 출력합니다. $k$ 번째 정수는 시상식 후 참가자 $k$ 가 가진 메달 개수입니다.

제한

$2 \leq N \leq 200\,000$ .
$1 \leq M \leq 200\,000$ .
$0 \le x_i, y_i \le N-1$ 이고 $x_i \neq y_i$ 입니다 (모든 $0 \le i \le M-1$ 에 대해).

힌트

첫 번째 예제에서는 대회 내내 누가 어떤 메달을 가졌는지 아래 그림이 보여 줍니다. 3일째에 참가자 1이 지면 그 참가자의 메달은 모두 참가자 2에게 넘어갑니다.

두 번째 예제는 아래 그림과 같습니다.

시상식 후 참가자 0은 메달 5와 6을, 참가자 1은 메달 3과 4를, 참가자 2는 메달 0, 1, 2를 받습니다.

예제3

예제 1
입력
```
3 4
0 1
2 1
1 0
2 1
```
예상 출력
```
1 1 2
```
예제 2
입력
```
3 7
0 1
0 2
2 0
0 1
1 0
2 0
0 2
```
예상 출력
```
2 2 3
```

예제 3

입력

예상 출력

5 0 1 1 1 2