UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4986. MiniumCut

统计 下载数据

Description

从前有张图。图里n个顶点两两之间有N^2种最小割。告诉你这N^2个最小割。还原出这张图。

Input

第一行一个正整数n,表示图的顶点数。
接下来n行每行N个非负整数,第i行第j列的数表示第i个点与第j个点的最小割。
点的编号从1开始。
Vi<=10^5,n<=100
保证vii=0。

Output

第一行一个整数m,表示图的边数。
接下来每行三个整数u,v,z。
表示从“到”存在一条权值为z的边。
l<=u,v<=N
0<Z<=10^9。
m<=n*(n-l)/2。
请注意你给出的图要求联通。
如果无解请输出-l。
若有多解则输出任意一组解。

Sample Input

3
0 2 2
2 0 2
2 2 0

Sample Output

2
2 3 2
1 3 2

Hint

请不要提交!


Source