Page Contents
Chef and Edge Flipping SOLUTION Codechef
Chef likes tournament graphs, which are directed graphs where each unordered pair of vertices is directly connected by exactly one edge. A directed graph is strongly connected if for each pair of vertices (a,b), there is a path from the vertex a to the vertex b.
Consider a tournament graph G with N vertices (numbered 1 through N). Chef takes a sequence of pairs of vertices (a1,b1),(a2,b2),…,(aM,bM) and does the following for each i from 1 to M in this order:
Flip the direction of the edge between vertices ai and bi.
If the graph is strongly connected either before or after flipping this edge, declare G a bad tournament.
If G is never declared a bad tournament, Chef calls it a good tournament. Given the sequence of M edge flips, find a good tournament.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M.
M lines follow. For each valid i, the i-th of these lines contains two space-separated integers ai and bi.
Output
For each test case, print N−1 lines. For each valid i, the i-th of these lines should contain N−i space-separated integers; for each valid j, the j-th of these integers should be 1 if there is an edge from the vertex i to the vertex i+j or 0 if there is an edge from the vertex i+j to the vertex i.
It can be proved that a good tournament always exists under the given constraints. If there are multiple solutions, you may print any one of them.
Constraints
1≤T≤400
6≤N≤400
the sum of N over all test cases does not exceed 4,000
Subtasks
Subtask #1 (30 points): M=N−2
Subtask #2 (40 points): M=⌈3N2⌉−3
Subtask #3 (30 points): M=2N−11
Example Input
1
6 4
1 3
3 4
2 6
5 6
Example Output
1 0 1 1 1
0 0 0 1
1 1 1
1 1
0
SOLUTION AFTER CONTEST
November Challenge 2020 SOLUTION CodeChef
- Selecting Edges SOLUTION SELEDGE
- Panic! at the Disco SOLUTION PANIC
- Restore Sequence SOLUTION RESTORE
October Lunchtime 2020 CodeChef SOLUTIONS