Graph Representation: Adjacency Matrix and Adjacency List

Given an undirected graph with $n$ vertices and $m$ edges, output the graph in two representations:

• An adjacency matrix of size $n \times n$ where the value at cell $(i, j)$ is 1 if there is an edge between vertex $i$ and vertex $j$, and 0 otherwise.
• An adjacency list for each vertex, listing all vertices adjacent to it in increasing order.

The vertices are numbered from 1 to $n$.

inputFormat

The first line contains two integers $n$ and $m$ separated by a space.

Each of the following $m$ lines contains two integers $u$ and $v$, representing an undirected edge between vertices $u$ and $v$.

outputFormat

First, output the adjacency matrix of the graph with $n$ lines. Each line contains $n$ integers separated by spaces.

After that, output the adjacency list of the graph in $n$ lines. The $i$th line should contain the neighbors of vertex $i$ in increasing order separated by a single space. If a vertex has no neighbors, output an empty line.

sample

3 3
1 2
2 3
1 3

0 1 1
1 0 1
1 1 0
2 3
1 3
1 2