#P11994. [2024年联测]图

    ID: 11144 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>图论拓扑排序CF2300构造模拟枚举最短路

[2024年联测]图

图(graph)

【题目描述】

有一个nn个点的竞赛图(即任意不同两点间恰有一条边的有向简单图)。

接下来有mm 次操作,每次给定两个不同的点 u,vu,v,然后将u,vu,v 之间的边反向(即, 若原来这条边是从uu指向vv 则改为vv 指向uu,反之亦然)。

如果在整个过程中,这个竞赛图没有成为过强连通图(即,任意时候,存在u,vu,v使得从uu开始没有到vv的路径),那么我们称这个图是好的。

现在给定了n,mn,m 和这mm 次操作的u,vu,v。请构造出一个好的竞赛图。

若有多个好的竞赛图,输出任意一个均算对。可以证明在本题条件下有至少一个好的竞赛图。

【输入格式】

从标准输入读入。

第一行,两个正整数n,mn,m。

接下来mm 行,第ii行两个不同的正整数u,vu,v,表示第ii次操作的点对。

【输出格式】

输出到标准输出。

输出n−1n-1 行。第ii 行包含n−in-i 个数,值均为00 或 11。

对于任意点对1≤u<v≤n1\le u<v\le n,若u,vu,v 间的边为uu指向vv,则第uu行第v−uv-u 个数是 11,否则是00。

样例输入

8 4
1 3
3 4
2 6
5 6

样例输出

0 0 0 0 0 0 0 
1 1 0 0 0 0 
0 0 0 0 0 
0 0 0 0 
0 0 0 
0 0 
0 

【数据范围】

本题比对方式为自定义校验器 (special judge)

对于所有数据,有 1≤n≤400,1≤m≤2n−111\le n\le 400,1\le m\le 2n-11。

子任务编号 分值 m≤m\le
1 30 n−2n-2
2 4040 ⌈3n2⌉−3\lceil\frac{3 n} {2} \rceil-3
33 3030 2n−112n-11