[XJTUPC2024] 瑟莉姆的宴会
题目背景
欢迎来到瑟莉姆大人的享乐宴会!
![](https://cdn.luogu.com.cn/upload/image_hosting/6kmpy10b.png)
题目描述
宴会中一共有 $n$ 个访客,编号 $1\sim n$。为了更好地控制影的力量,瑟莉姆要求有 $n-1$ 个访客都恰好受到另一个访客的支配,而剩下的那个人成为总支配者,支配其他 $n-1$ 名访客。访客间的**直接支配关系**构成了一棵有根树。
对于这棵树来说,若结点 $a$ 的父结点是 $b$,那么称 $b$ 支配了 $a$,同时称 $b$ 是 $a$ 的**直接支配者**。同时,支配的关系具有**传递性**,即若 $a$ 支配 $b$,$b$ 支配 $c$,那么 $a$ 也就支配了 $c$。
另外有 $m$ 个支配条件,一个支配条件是一个有序二元组 $(x,y)$ ($1 \le x,y \le n$,$x\neq y$),若访客 $x$ 支配 $y$,那么影的力量会增加 $1$ 点;若 $y$ 支配 $x$ ,那么影的力量会减少 $1$ 点。若两者互不支配,那么影的力量不变。初始的影的力量是 $0$。
作为贴心仆人的松雀需要组织一场宴会,那么需要为宴会中的每个人安排支配关系。由于瑟莉姆大人不需要关心影的力量能够达到多大,只需要让影的力量保持非负,你能够帮助她构造最终的支配关系吗?
若存在多个解,你只需要输出任意一个。保证对于任何合法输入,均存在解。
输入输出格式
输入格式
第一行输入两个正整数 $n,m$ ($1\le n \le 1\times 10^5,\ 1 \le m \le 2\times 10^5$),表示访客数量和支配条件数,用空格隔开。
接下来 $m$ 行,每行两个用空格分隔的正整数 $x,y$ ($1 \le x,y \le n,\ x\neq y$),表示一个支配条件的二元组 $(x,y)$。支配条件可能会重复,也可能会出现相反的支配条件,即既出现了 $(x,y)$,也出现了 $(y,x)$。支配条件两两互不影响。
输出格式
输出一行 $n$ 个数,第 $i$ 个数表示编号为 $i$ 的访客的直接支配者编号。总支配者的直接支配者编号为 $0$。
输入输出样例
输入样例 #1
5 5
3 1
2 3
1 3
2 4
3 5
输出样例 #1
2 3 0 3 3
说明
样例中最终影的力量是 $1-1-1+0+1=0$,符合非负条件。