UOJ Logo

NOI.AC

1S 512MB

#95. cycle

统计

正环(cycle)

问题描述

给定一个n个点m对边的无自环无重边的有向图,求边数最少的正环。

输入格式

第一行包含2个整数n,m,表示这张图有n个点m对边。 接下来m行,每行包括4个整数u,v,c1,c2,表示u到v边权为c1,v到u边权为c2。

输出格式

输出一个数,为边数最少的正环的边数,如果没有正环则输出0。

输入样例1

3 3
1 2 -10 30
1 3 1 1
2 3 -10 -1

输出样例1

2

输入样例2

4 6
1 2 -65 -53
1 3 -64 -19
1 4 -77 -64
2 3 -20 8
2 4 -11 -61
3 4 -39 -8

输出样例2

0

数据规模与约定

对于20的数据n50

对于50的数据n100

对于100的数据1n3001mn(n1)/2