그래프는 정점과 정점을 잇는 간선으로 정의된 자료 구조이다. 그림으로 그래프를 표현할 때, 정점은 보통 원으로 표현하고 간선은 원을 잇는 선으로 표현한다. 위 그래프에서 정점은 1, 2, 3, 4, 5, 6이고 간선은 ~(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)~이다.

수학적으로는 그래프를 위와 같이 정의할 수 있으나, 실제 프로그램으로 그래프를 저장하는 방법은 여러 가지가 있다. 인접 행렬(Adjacency matrix)이란 그러한 방법 중 하나로, 행렬(2차원 배열)을 통해서 그래프를 표현하는 방법이다. 예를 들어 2차원 배열 adj[i][j]를 정의한 후에 그래프에서 정점 u에서 v를 잇는 간선이 있다면 adj[i][j] = 1 아니면 adj[i][j] = 0을 저장하게 하면 된다.

예를 들어 위 그래프의 간선을 모두 저장하고 난 후의 인접 행렬(Adjacency matrix)은 위와 같다. 위 그래프의 간선은 방향이 없기 때문에 adj[i][j] = 1이라면 반대로 adj[j][i] = 1이다.

그래프가 주어질 때, 이를 인접 행렬(Adjacency matrix)로 표현해보자.

입력

첫째 줄에 그래프의 정점의 개수와 간선의 개수 ~N, M(1 \le N, M \le 50)~이 주어진다. 그래프의 각 정점에는 1부터 N까지 번호가 매겨져 있다.

둘째 줄부터 M개의 줄에 그래프의 간선이 주어진다. 간선은 서로 다른 두 정점 ~u, v(1 \le u, v \le N)~를 잇는다. 주어지는 그래프는 단순 그래프(Simple graph)이다. 따라서 두 정점을 잇는 간선은 최대 한 개 존재할 수 있으며, 자기 자신을 잇는 간선은 없다.

출력

주어진 그래프를 표현한 인접 행렬(Adjacency matrix)을 출력한다.

예제 입력 1

6 7
1 2
1 5
2 3
2 5
3 4
4 5
4 6

예제 출력 1

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

예제 입력 2

4 2
1 2
2 3

예제 출력 2

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

예제 입력 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

예제 출력 3

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

노트

N \times N 크기의 2차원 배열을 선언한 후에 M개의 간선을 입력받으면서 배열을 채워줍니다.

배열은 0으로 초기화한 후에 간선으로 ~(u, v)~가 주어지면 adj[i][j]에 1을 대입합니다. 반대도 마찬가지로 대입해줘야 함에 유의합니다.