Algebraic Representations of a Graph

Given an undirected graph with n vertices and m edges, which may include parallel edges and self-loops, you are required to output its complete algebraic representations. In this problem, you need to construct and print both the adjacency matrix and the Laplacian matrix of the graph.

Note:

• The graph is 1-indexed.
• For an edge (u, v):
• If u ≠ v, increase A[u][v] and A[v][u] by 1.
• If u = v (self-loop), increase A[u][u] by 1.
• For the Laplacian matrix L, the diagonal entry L[i][i] is equal to the degree of vertex i. The degree is computed as the sum of A[i][j] for j ≠ i plus twice A[i][i] (since a self-loop contributes 2 to the degree). For off-diagonal entries where i ≠ j, L[i][j] = -A[i][j].

inputFormat

The first line contains two space-separated integers n and m — the number of vertices and edges respectively.

The following m lines each contain two space-separated integers u and v indicating an edge between vertices u and v.

outputFormat

First, print the adjacency matrix of the graph: n lines where each line contains n integers separated by spaces.

Then, print an empty line followed by the Laplacian matrix of the graph: again, n lines where each line contains n integers separated by spaces.

sample

3 3
1 2
2 3
2 2

0 1 0
1 1 1
0 1 0
1 -1 0
-1 4 -1
0 -1 1