Given the nodes and edges of a graph, calculate the adjacency matrix for the graph.

You have a graph with n nodes indexed from 0 to n-1. You also have m bi-directional edges each connecting a couple of nodes.

You have to return the adjacency matrix for the given graph.

Example

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has the following lines:

• The first line contains two space-separated integers n and m.
• The next m lines contain two space-separated integers each denoting the edges.

Output Format

For each test case, the output has n lines denoting the adjacency matrix of the graph.

Sample Input

2
4 4
0 1
0 2
2 3
0 3
4 5
0 1
2 0
2 3
3 3
0 3

Expected Output

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

Constraints

1 <= T <= 10
1 <= n <= 500
0 <= m <= n2