路径数量

题目描述

给定$n+1$个点$m$条边的有向图，求每个点到点$n+1$的不同方式数，其中不同的定义是：每条边可以走多次，如果走边的顺序有一条不同即称两种方式不同。求到达点$n+1$的方式最多的点到点$n+1$的方式数，以及有多少个点有这么多方式，按照顺序输出点的编号。

如果最多不同方式超过了$36500$那么视做全部相等，方法数输出$zawsze$。

输入格式

第$1$行，两个正整数$n$，$m$。

第$2$至$m+1$行，两个正整数$u$，$v$，代表存在一条点$u$通向点$v$的边，可能有自环。

输出格式

第$1$行，一个正整数，代表到达点$n+1$方式最多的点到达点$n+1$的方法数。

第$2$行，一个正整数$k$，代表有多少个点有这么多方式。

第$3$行，从小到大$k$个正整数，代表拥有最多达到点$n+1$方式的点的编号（不要输出$n+1$）。

数据范围与提示

• 对于$60\%$的数据，$1 \leq n$，$m \leq 100$；
• 对于$100\%$的数据，$1 \leq n$，$m \leq 10^{6}$。

样例

3 5
1 2
1 3
2 3
3 4
3 4

4
1
1

见path2.in

见path2.out