Algorithms and Data Structures

Adjacency Matrix - Graph Representation

A graph is a structure that consists of vertices (nodes) and edges that connect these vertices. Graphs can be used to model relationships between objects or to represent a network. They are often used to represent connections between cities, people, or even abstract entities.
Graphs can be either directed or undirected:
  1. Directed graphs: All the edges have a direction, meaning that there is a “road” from one vertex to another but there might not be one going back. Similar to a one-way road.
      2. Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).
A directed graph with 8 edges and 10 edges. Notice that vertices 5 and 8 have a bidirectional connection.
A directed graph with 8 edges and 10 edges. Notice that vertices 5 and 8 have a bidirectional connection.
  1. Undirected graphs: The edges don’t have a direction, which means that if there is an edge between two vertices, those vertices are connected to each other (in both directions).
An undirected graph with 8 vertices and 9 edges
An undirected graph with 8 vertices and 9 edges
One of the ways to represent a graph is with Adjacency Matrix. It’s a square matrix representing the whole graph. Each row and column in the matrix corresponds to a vertex in the graph. If there is an edge between two vertices, the corresponding entry in the matrix is set to 1. Otherwise, it is set to 0.
An adjacency matrix for the directed graph presented above can look like this:
g = [
#  1  2  3  4  5  6  7  8
  [0, 1, 0, 1, 0, 0, 0, 0],   # connections going out from the vertex 1
  [0, 0, 0, 0, 1, 0, 0, 0],   # connections going out from the vertex 2
  [0, 1, 0, 0, 0, 0, 0, 0],   # connections going out from the vertex 3
  [0, 0, 0, 0, 0, 0, 0, 0],   # connections going out from the vertex 4
  [0, 0, 0, 0, 0, 1, 0, 1],   # connections going out from the vertex 5
  [0, 0, 0, 1, 0, 0, 1, 0],   # connections going out from the vertex 6
  [0, 0, 0, 0, 0, 0, 0, 1],   # connections going out from the vertex 7
  [0, 0, 0, 0, 1, 0, 0, 0],   # connections going out from the vertex 8
]
Notice that for a bidirectional edge, both 1s are present for both vertices.
Also, note that we have changed the indexing of the edges. So, if we access the g[0], it would actually return all the connections of the node with index 1. We could’ve used 9 rows and 9 columns instead of 8 and have a one-to-one matching between the numbers in the image and the indexing of the matrix g, but that’s up to you 😎.

Challenge: Edges to Adjacency Matrix

Given a graph with v vertices and e edges, you are asked to obtain its adjacency matrix.

Input

The first line of the input contains two integers v (1 ≤ v ≤ 1000) and e (1 ≤ e ≤ 100 000).
The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.

Output

The program should print the adjacency matrix of the given graph. The values in each row should be separated by a space.

Examples

Input
Output
8 9 1 4 4 6 3 2 2 1 5 2 5 6 8 5 7 6 7 8
0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 5 MB

To check your solution you need to sign in
Sign in to continue