Construct the adjacency matrix of an undirected simple graph.

Input

The first line contains n and m. Each of the next m lines contains an edge u v.

• 1 <= n <= 1000
• 0 <= m <= n(n-1)/2

Output

Print the n by n adjacency matrix. Separate adjacent entries by one space.

Example

Input

4 3
1 2
2 3
1 4

Output

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