#P11994. [2024年联测]图
[2024年联测]图
图(graph)
【题目描述】
有一个个点的竞赛图(即任意不同两点间恰有一条边的有向简单图)。
接下来有 次操作,每次给定两个不同的点 ,然后将 之间的边反向(即, 若原来这条边是从指向 则改为 指向,反之亦然)。
如果在整个过程中,这个竞赛图没有成为过强连通图(即,任意时候,存在使得从开始没有到的路径),那么我们称这个图是好的。
现在给定了 和这 次操作的。请构造出一个好的竞赛图。
若有多个好的竞赛图,输出任意一个均算对。可以证明在本题条件下有至少一个好的竞赛图。
【输入格式】
从标准输入读入。
第一行,两个正整数。
接下来 行,第行两个不同的正整数,表示第次操作的点对。
【输出格式】
输出到标准输出。
输出 行。第 行包含 个数,值均为 或 。
对于任意点对,若 间的边为指向,则第行第 个数是 ,否则是。
样例输入
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 | 30 | |
| 2 | ||