#P17938. Shiroi Album II
Shiroi Album II
Shiroi Album II
给定一个带正整数边权的无向图。满足下列条件的路径称为三角路径:
- 路径不超过两条边;或
- 对路径上任意三条不同的边,它们的边权都能构成一个非退化三角形。
正整数 能构成三角形,当且仅当 、、 同时成立。
请判断每一对顶点 之间是否存在三角路径。规定每个顶点到自身总有三角路径。图可以不连通,可以有自环和重边。
输入格式
第一行是测试用例数 ,。
每组用例第一行包含 ,表示顶点数与边数。接下来 行,每行三个整数 ,表示一条无向边及其边权。
- ;
- ,;
- 一个输入文件内,,。
输出格式
每组用例输出 行,每行恰好 个字符。第 行第 个字符为 1 表示存在从 到 的三角路径,否则为 0。
样例 1
2
4 3
1 2 2
2 3 2
3 4 3
8 7
1 2 3
2 3 4
3 4 1
3 5 2
2 6 2
6 7 4
6 8 5
1111
1111
1111
1111
11101110
11111111
11111111
01111000
11111000
11100111
11100111
01100111