小W在上数理逻辑的课。他想要自创一套公理系统。

现在小W有 $n$ 个命题，标号为 $1-n$，他有 $m$ 个推出关系。每个推出关系都是形如 $P \Rightarrow Q$，意思是如果 $P$ 被证明是对的，那么就可以推出 $Q$ 是对的。你可以把这些推出关系想成一个有向图。他发现这张图没有环。他现在想要从中选出一些命题设为公理，要求其它所有命题都可以通过这些公理推出。他想要最小化选出的公理数，并输出任意一种方案即可。

小W给出公理之后，小W的朋友小Y想要通过这些公理去证明所有命题。对于每一个命题 $T$，他想要用最少的推导次数证明这个命题。即找一条路径 $v_1,v_2,\dots,v_k=T$，满足 $v_1$ 是一条公理，并且 $\forall\ i \in [1,k-1],\ v_i \Rightarrow v_{i+1}$，则推导次数是 $k-1$。

输入格式

第一行两个整数 $n, m$。 接下来 $m$ 行，每行两个整数 $P,Q$，表示第 $P$ 个命题可以推出第 $Q$ 个命题。

输出格式

第一行一个整数 $k$，表示公理的个数。 第二行 $k$ 个整数，表示选出的公理，按从小到大输出。 第三行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个命题的最少推导次数。

样例1

input

7 6
1 3
2 3
3 4
3 5
4 6
5 6

output

3
1 2 7
0 0 1 2 2 3 0

样例2

见下载文件。

限制与约定

对于 $20\%$ 的数据，$n, m \le 15$。

对于 $60\%$ 的数据，$n, m \le 1000$。

对于 $100\%$ 的数据，$1 \le n, m \le 5 * 10^5$。

时间限制：2 s

空间限制：512 MB

提示

本题输入输出量较大，请选择较快的读入方式。

下载

样例数据下载