방향 그래프(Directed Graph)는 정점(Vertex)들과 한 정점에서 다른 정점으로 방향이 있는 간선(Edge)들로 이루어진 자료구조입니다.

이러한 그래프를 컴퓨터에서 표현하는 대표적인 방법 중 하나가 바로 인접 행렬(Adjacency Matrix)입니다.

V개의 정점과 E개의 간선 정보가 주어졌을 때, 이 그래프를 인접 행렬로 표현하는 프로그램을 작성하시오.

인접 행렬 A의 각 원소 A[i][j]는 다음과 같이 정의됩니다.

• i번 정점에서 j번 정점으로 가는 간선이 존재하면 1
• 존재하지 않으면 0

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 공백을 사이에 두고 주어진다.

둘째 줄부터 E개의 줄에 걸쳐 각 간선의 시작 정점 u와 도착 정점 v가 공백을 사이에 두고 주어진다.

이는 u에서 v로 가는 방향성 간선이 존재함을 의미한다. (이 문제에서는 동일한 간선이 중복되어 주어지지 않는다.)

출력

첫째 줄부터 V개의 줄에 걸쳐 인접 행렬을 출력한다. 각 줄에는 1번 정점부터 V번 정점까지의 연결 상태를 공백으로 구분하여 출력해야 한다.

제한 사항

• 1 ≤ V ≤ 100
• 0 ≤ E ≤ V × (V - 1)
• 1 ≤ u, v ≤ V (단, u ≠ v 이며, 자기 자신으로 향하는 간선은 없다.)

예제 입력 1

4 4
1 2
1 3
3 4
4 1

예제 출력 1

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