# Chef and Edge Flipping SOLUTION EFLIP

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

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
{"ft_lang_label":"__label__en","ft_lang_prob":0.8308788,"math_prob":0.9123165,"size":2078,"snap":"2021-43-2021-49","text_gpt3_token_len":559,"char_repetition_ratio":0.11909354,"word_repetition_ratio":0.05319149,"special_character_ratio":0.25649664,"punctuation_ratio":0.09009009,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99146146,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-12-08T13:01:52Z\",\"WARC-Record-ID\":\"<urn:uuid:3e7edeaf-f8c7-40ac-8824-a4ced0017dda>\",\"Content-Length\":\"136925\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b3d3862e-54ed-415b-88da-26edf921f4ae>\",\"WARC-Concurrent-To\":\"<urn:uuid:0f5bcb65-6590-4512-b4e2-0208d80bcb29>\",\"WARC-IP-Address\":\"172.67.153.85\",\"WARC-Target-URI\":\"https://cybergeeksquad.co/2020/10/chef-and-edge-flipping-solution-eflip.html\",\"WARC-Payload-Digest\":\"sha1:LBK5GJKZOVZZ7QJHHRLAR65NKGFHJI34\",\"WARC-Block-Digest\":\"sha1:4ID54JSYFQXIVUMB3NXKVIFUHXXXYSKA\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964363510.40_warc_CC-MAIN-20211208114112-20211208144112-00447.warc.gz\"}"}