#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream input("input.txt");
    int n = 0;
    int m = 0;
    input >> n >> m;
    int** adjMatrix = new int* [n];
    for (int i = 0; i < n; ++i) {
        adjMatrix[i] = new int[n];
        for (int j = 0; j < n; ++j) {
            adjMatrix[i][j] = 0;
        }
    }
    int u, v;
    for (int i = 0; i < m; ++i) {

        input >> u >> v;
        adjMatrix[u - 1][v - 1] = 1;
        adjMatrix[v - 1][u - 1] = 1;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
    int end = n + 2 * m + 1;
    int* imas = new int[end];
    imas[0] = n;
    for (int i = 1; i < end; ++i) {
        imas[i] = -1;
    }
    int k1 = n + 1;
    int i1 = 1;
    bool Flag = false;
    for (int i = 0; i < n; ++i) {
        Flag = false;
        for (int j = 0; j < n; ++j) {
            if (adjMatrix[i][j] == 1) {
                cout << k1 << " " << i << " " << j << " " << adjMatrix[i][j] << endl;
                if (!Flag) {
                    imas[i+1] = k1;
                    Flag = true;
                }
                imas[k1] = j + 1;
                k1++;
            }
        }
    }
    for (int i = 0; i < end; ++i) {
        cout << imas[i] << " ";
    }
}