#Pscc18. 4.路径数量

    ID: 604 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>强连通分量赛制:OI来源:wyfoj http://127.0.0.1

4.路径数量

4.路径数量

题目描述

给定个n+1点m条边的有向图,求每个点到点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方式的点编号,从小到大。

数据范围

(原站未提供,导入后需人工补齐)

样例

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

提示

对于60%的数据,1<=n,m<=100。

对于100%的数据,1<=n,m<=10^6。