时空限制

1S/512M

题目描述

一个通信网络由 $n$ 个中继站和 $m$ 条双向通信线路组成，中继站依次编号为 $1$ 到 $n$。网络中没有自环和重边，每个中继站都至少连接一条通信线路，但网络不一定连通。

每个中继站 $i$ 都需要从与其直接相连的中继站中选择一个作为转发目标，记为 $p_i$。之后，中继站 $i$ 接收到的所有信息都会转发给中继站 $p_i$，由此形成 $n$ 条有向转发关系 $i\to p_i$。

若存在 $k\ge 2$ 个互不相同的中继站 $v_1,v_2,\ldots,v_k$，满足 $p_{v_i}=v_{i+1}$（$1\le i<k$）且 $p_{v_k}=v_1$，则称这些中继站组成一个长度为 $k$ 的转发环。

一个中继站是不稳定的，当且仅当它位于某个转发环上。即使一个中继站的信息最终会进入某个转发环，只要它本身不在环上，它仍然是稳定的。

请为每个中继站选择转发目标，使不稳定中继站的数量最少，并输出任意一种达到最小值的选择方案。

格式

输入格式

第一行包含两个整数 $n,m$，表示中继站数量和通信线路数量。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示中继站 $u$ 与中继站 $v$ 之间有一条双向通信线路。

输出格式

第一行输出一个整数，表示不稳定中继站数量的最小值。

第二行输出 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示你的选择方案。对于每个 $1\le i\le n$，中继站 $p_i$ 必须与中继站 $i$ 直接相连，且该方案产生的不稳定中继站数量必须等于第一行输出的最小值。

若存在多种合法方案，输出任意一种即可。

样例

样例输入 #1

5 3
1 2
2 3
4 5

样例输出 #1

4
2 1 2 5 4

样例解释 #1

中继站 $1,2$ 和中继站 $4,5$ 分别组成一个转发环，因此不稳定中继站为 $1,2,4,5$。

数据规模

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 $100\%$ 的数据，满足 $2\le n\le 2\times10^5$，$1\le m\le\min\left(2\times10^5,\frac{n(n-1)}{2}\right)$，$1\le u,v\le n$，$u\ne v$。保证不存在重复的通信线路，且每个中继站都至少连接一条通信线路。