#Pscc18. 4.路径数量
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。