有 n 个集合,编号从 1 到 n。一开始第 i(1\le i\le n) 个集合 S_i 只有第 i 号元素。接下来进行 m 次操作,每次操作选定当前第 u,v(1\le u,v\le n) 个集合 S_u,S_v,并更改这两个集合为 S_u=S_v=S_u\cup S_v。每次操作建立在上一次操作的基础上。问全部操作结束后有多少个集合拥有全部 n 个元素,升序输出所有这些集合的编号。若没有一个集合满足,输出 -1
。
输入
输入一行两个整数 n,m(2\le n\le5\times10^4,1\le m\le5\times10^4)。
接下来输入 m 行,每行两个整数 u,v(1\le u,v\le n,u\neq v)。
输出
输出一行若干个整数,代表集合编号或 -1
。
样例
标准输入 复制文本 |
5 4 1 2 2 3 3 4 4 5 |
标准输出 复制文本 |
4 5 |
标准输入 复制文本 |
5 4 2 3 3 4 1 2 2 5 |
标准输出 复制文本 |
-1 |
提示
如果觉得这道题太简单,可以做一下 这道题。本题的出题思路节选自这道题的部分解答过程。