From the list of edges to the adjacency matrix - 2

A simple directed graph is described by a list of edges.

Your task is to output its representation as an adjacency matrix.

Input

The first line of the input contains two integers: N (1 ≤ N ≤ 100), representing the number of vertices, and M (1 ≤ M ≤ N·(N-1)/2), representing the number of edges. The following M lines each contain a pair of numbers, specifying one edge of the graph.

Output

Output the adjacency matrix of the graph.

Examples