{"problem":{"name":"[XJTUPC 2024] 瑟莉姆的宴会","description":{"content":"宴会中一共有 $n$ 个访客，编号 $1\\sim n$。为了更好地控制影的力量，瑟莉姆要求有 $n-1$ 个访客都恰好受到另一个访客的支配，而剩下的那个人成为总支配者，支配其他 $n-1$ 名访客。访客间的**直接支配关系**构成了一棵有根树。 对于这棵树来说，若结点 $a$ 的父结点是 $b$，那么称 $b$ 支配了 $a$，同时称 $b$ 是 $a$ 的**直接支配者**。同时，支配的关系具","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10521"},"statements":[{"statement_type":"Markdown","content":"宴会中一共有 $n$ 个访客，编号 $1\\sim n$。为了更好地控制影的力量，瑟莉姆要求有 $n-1$ 个访客都恰好受到另一个访客的支配，而剩下的那个人成为总支配者，支配其他 $n-1$ 名访客。访客间的**直接支配关系**构成了一棵有根树。\n\n对于这棵树来说，若结点 $a$ 的父结点是 $b$，那么称 $b$ 支配了 $a$，同时称 $b$ 是 $a$ 的**直接支配者**。同时，支配的关系具有**传递性**，即若 $a$ 支配 $b$，$b$ 支配 $c$，那么 $a$ 也就支配了 $c$。\n\n另外有 $m$ 个支配条件，一个支配条件是一个有序二元组 $(x,y)$ ($1 \\le x,y \\le n$，$x\\neq y$)，若访客 $x$ 支配 $y$，那么影的力量会增加 $1$ 点；若 $y$ 支配 $x$ ，那么影的力量会减少 $1$ 点。若两者互不支配，那么影的力量不变。初始的影的力量是 $0$。\n\n作为贴心仆人的松雀需要组织一场宴会，那么需要为宴会中的每个人安排支配关系。由于瑟莉姆大人不需要关心影的力量能够达到多大，只需要让影的力量保持非负，你能够帮助她构造最终的支配关系吗？\n\n若存在多个解，你只需要输出任意一个。保证对于任何合法输入，均存在解。\n\n## Input\n\n第一行输入两个正整数 $n,m$ ($1\\le n \\le 1\\times 10^5,\\ 1 \\le m \\le 2\\times 10^5$)，表示访客数量和支配条件数，用空格隔开。\n\n接下来 $m$ 行，每行两个用空格分隔的正整数 $x,y$ ($1 \\le x,y \\le n,\\ x\\neq y$)，表示一个支配条件的二元组 $(x,y)$。支配条件可能会重复，也可能会出现相反的支配条件，即既出现了 $(x,y)$，也出现了 $(y,x)$。支配条件两两互不影响。\n\n## Output\n\n输出一行 $n$ 个数，第 $i$ 个数表示编号为 $i$ 的访客的直接支配者编号。总支配者的直接支配者编号为 $0$。\n\n[samples]\n\n## Background\n\n欢迎来到瑟莉姆大人的享乐宴会！\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/6kmpy10b.png)\n\n## Note\n\n样例中最终影的力量是 $1-1-1+0+1=0$，符合非负条件。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10521","tags":["2024","Special Judge","O2优化","高校校赛"],"sample_group":[["5 5\n3 1\n2 3\n1 3\n2 4\n3 5\n","2 3 0 3 3 "]],"created_at":"2026-03-03 11:09:25"}}