Medal Possession Tournament

There are \(N\) contestants numbered from \(0\) to \(N-1\) participating in a cage tennis tournament lasting \(M\) days. Exactly one match is played per day. In this tournament, a total of \(M\) medals are created; a new medal is created and awarded in every match.

On day \(i\) (where \(0\le i\le M-1\)), two contestants \(x_i\) and \(y_i\) play a match. During the match the following events occur:

1. Contestant \(x_i\) defeats contestant \(y_i\).
2. A new medal (medal \(i\)) is created and awarded to the winner \(x_i\).
3. All medals currently held by the loser \(y_i\) are transferred to the winner \(x_i\).

After day \(M-1\), on day \(M\) an awarding ceremony is held. In the ceremony, for each medal \(i\) (\(0\le i\le M-1\)) the medal is finally awarded to the contestant who held that medal for the greatest total number of nights (the durations of possession are not necessarily consecutive). In the event of a tie, the medal is awarded to the contestant with the smallest number.

Assume that at the end of every day (after the match and any medal transfers) each medal in existence is held by someone through the night, and that night counts are accumulated over the tournament. Your task is to determine, at the awarding ceremony, how many medals each contestant receives.

Note: During simulation, after each day all medals (both newly created and those carried over) get their current holder's night count incremented by 1.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space. Each of the next \(M\) lines contains two integers \(x_i\) and \(y_i\) representing the participants of the match on day \(i\), where \(x_i\) is the winner and \(y_i\) is the loser.

outputFormat

Output a single line with \(N\) integers separated by spaces. The \(i\)th integer represents the number of medals awarded to contestant \(i\) at the ceremony.

sample

3 3
0 1
1 2
2 0

1 1 1