正环(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%$的数据$n \le 50$

对于$50%$的数据$n \le 100$

对于$100%$的数据$1 \le n \le 300$，$1 \le m \le n*(n-1) / 2 $