#include <bits/stdc++.h>
using namespace std;
// Using descriptive types
typedef long long ll;
const int MAX_PLAYERS = 200005;
// Global structures for the DFS
vector<int> adj[MAX_PLAYERS]; // The "Medal Transfer" Tree
ll nights_held[MAX_PLAYERS]; // How many nights a player held the current medal
int medal_winners[MAX_PLAYERS]; // how many prizes each player won
int winner_on_day[MAX_PLAYERS]; // A[i] from the input: who won on day i
// A set to keep track of who held the medal the most nights.
// Stores {nights, -player_id} so the largest nights are at the end.
set<pair<ll, int>> ranking;
void update_ranking(int player, ll days_delta) {
ranking.erase({nights_held[player], -player});
nights_held[player] += days_delta;
ranking.insert({nights_held[player], -player});
}
void solve_medal_history(int match_idx, int total_matches) {
// Determine who currently has the most nights for this specific medal path
// prev(ranking.end()) gives us the pair with the highest 'nights'
int leader = -prev(ranking.end())->second;
medal_winners[leader]++;
for (int prev_match : adj[match_idx]) {
// Calculate duration: how long did the winner of 'prev_match'
// hold the medal before 'match_idx' happened?
ll duration = match_idx - prev_match;
update_ranking(winner_on_day[prev_match], duration);
solve_medal_history(prev_match, total_matches);
// Backtrack: remove the duration so it doesn't affect other branches
update_ranking(winner_on_day[prev_match], -duration);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int num_players, num_matches;
cin >> num_players >> num_matches;
vector<int> loser_on_day(num_matches);
vector<int> last_match_won_by(num_players, -1);
vector<bool> is_final_match(num_matches, true);
for (int i = 0; i < num_matches; i++) {
cin >> winner_on_day[i] >> loser_on_day[i];
// Winner i takes medals from their own last win...
if (last_match_won_by[winner_on_day[i]] != -1) {
int prev_m = last_match_won_by[winner_on_day[i]];
adj[i].push_back(prev_m);
is_final_match[prev_m] = false;
}
// ...and from the loser's last win.
if (last_match_won_by[loser_on_day[i]] != -1) {
int prev_m = last_match_won_by[loser_on_day[i]];
adj[i].push_back(prev_m);
is_final_match[prev_m] = false;
}
// Update the state: Winner is now at match i, Loser has no "active" medals
last_match_won_by[winner_on_day[i]] = i;
last_match_won_by[loser_on_day[i]] = -1;
}
// Initialize ranking set with all players having 0 nights
for (int i = 0; i < num_players; i++) {
ranking.insert({0, -i});
}
// A medal is "final" if it wasn't passed to a later match winner
for (int i = num_matches - 1; i >= 0; i--) {
if (is_final_match[i]) {
// A final medal is held from day 'i' until the end of the tournament (num_matches)
ll final_stretch = num_matches - i;
update_ranking(winner_on_day[i], final_stretch);
solve_medal_history(i, num_matches);
update_ranking(winner_on_day[i], -final_stretch);
}
}
for (int i = 0; i < num_players; i++) {
cout << medal_winners[i] << (i == num_players - 1 ? "" : " ");
}
cout << endl;
return 0;
}
