{"problem":{"name":"[EGOI 2023] Padel Prize Pursuit / 追梦笼式网球","description":{"content":"有 $N$ 个编号为 $0$ 到 $N-1$ 的选手参加一场 $M$ 天的笼式网球锦标赛。每天恰好进行一次比赛。在锦标赛中共颁发 $M$ 块奖牌，每场比赛颁发一块新奖牌。在第 $i$ 天的比赛中（$0\\le i\\le M-1$），两名编号分别为 $x_i$ 和 $y_i$ 的选手参加。比赛中发生如下事件： - 选手 $x_i$ 打败选手 $y_i$。 - 一个新的奖牌授予给获胜者 $x_i$。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9464"},"statements":[{"statement_type":"Markdown","content":"有 $N$ 个编号为 $0$ 到 $N-1$ 的选手参加一场 $M$ 天的笼式网球锦标赛。每天恰好进行一次比赛。在锦标赛中共颁发 $M$ 块奖牌，每场比赛颁发一块新奖牌。在第 $i$ 天的比赛中（$0\\le i\\le M-1$），两名编号分别为 $x_i$ 和 $y_i$ 的选手参加。比赛中发生如下事件：\n\n- 选手 $x_i$ 打败选手 $y_i$。\n- 一个新的奖牌授予给获胜者 $x_i$。\n- 失败者所有现有的奖牌都授予给获胜者。\n\n在第 $M$ 天（最后一场比赛结束后一天）举行颁奖典礼。在颁奖典礼上，所有奖牌被收集起来，并授予给持有该奖牌时间最长的选手。具体地，在第 $M$ 天，奖牌 $i$ 授予给持有奖牌 $i$ 最多个晚上的选手（不必须连续持有）。如果两个或更多选手持有一个奖牌同样多晚上，奖牌授予给其中编号最小的选手。\n\n你的任务是求出颁奖典礼中，每位选手被授予多少奖牌。\n\n## Input\n\n第一行两个整数 $N,M$，表示选手数和比赛数。\n\n接下来 $M$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 天的比赛中，选手 $x_i$ 打败选手 $y_i$。\n\n## Output\n\n一行 $N$ 个整数，第 $k$ 个整数表示颁奖典礼中，第 $k$ 位选手被授予的奖牌数。\n\n[samples]\n\n## Background\n\nDay 1 Problem B.\n\n题面译自 [EGOI2023 ppp](https://egoi23.se/assets/tasks/day1/ppp.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n## Note\n\n**样例 $1$ 解释**\n\n下图展示了样例 $1$ 中锦标赛期间奖牌的归属。当选手 $1$ 在第三天被打败时，她的所有奖牌都被授予给选手 $2$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/jex0m4dg.png)\n\n---\n\n**样例 $2$ 解释**\n\n如下图。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/nyujve0b.png)\n\n在颁奖典礼中，选手 $0$ 被授予奖牌 $5$ 和 $6$，选手 $1$ 被授予奖牌 $3$ 和 $4$，选手 $2$ 被授予奖牌 $0,1,2$。\n\n---\n\n**数据范围**\n\n对于全部数据，$2\\le N\\le 2\\times 10^5$，$1\\le M\\le 2\\times 10^5$，$0\\le x_i,y_i\\le N-1$ 且 $x_i\\ne y_i$。\n\n- 子任务一（$12$ 分）：$N=2$。\n- 子任务二（$16$ 分）：$N,M\\le 2\\times 10^3$。\n- 子任务三（$15$ 分）：第 $i$ 场比赛的获胜者参加了第 $i+1$ 场比赛，依赖子任务一。\n- 子任务四（$20$ 分）：在第 $i$ 场比赛时，$x_i$ 有至少和 $y_i$ 一样多的奖牌。\n- 子任务五（$22$ 分）：一旦一名选手被打败，她永远不会再次参赛。\n- 子任务六（$15$ 分）：无特殊限制，依赖子任务二、三、四、五。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9464","tags":["2023","O2优化","EGOI（欧洲/女生）"],"sample_group":[["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"]],"created_at":"2026-03-03 11:09:25"}}