#include <iostream>
#include<bits/stdc++.h>

using namespace std;

int main() {
    int N;
    int V;
    int **M, **M_copy, *D, *S, *L, **res;
    ifstream fin("fin.txt");
    ofstream fout("output.txt");
    fin >> N >> V;
    N = N + 1;
    M = new int *[N];
    M_copy = new int *[N];
    for (int i = 0; i < N; i++) {
        M_copy[i] = new int[N];
        for (int j = 0; j < N; j++) {
            M_copy[i][j] = 0;
        }
    }
    for (int i = 0; i < N; i++) {
        M[i] = new int[N];
        for (int j = 0; j < N; j++) {
            M[i][j] = 0;
        }
    }
    for (int i = 0; i < V; i++) {
        int a, b;
        fin >> a >> b;
        M[a][b] = 1;
        M[b][a] = 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            fout << M[i][j] << ' ';
        }
        fout << endl;
    }
    fin.close();
    fout.close();
    fin.open("output.txt");
    fout.open("output2.txt");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            fin >> M_copy[i][j];
        }
    }
    S = new int[N];
    L = new int[N];
    D = new int[N*N];
    S[1] = 1;
    int ind = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if(M[i][j] == 1){
                D[ind] = j;
                L[i]++;
                ind++;
            }
        }
        if(i >= 2){
            S[i] = S[i-1] + L[i-1];
        }
    }
    fout << N*N << endl;
    for(int i=1; i < N*N; i++){
        fout << D[i] << ' ';
    }
    fout << endl;
    fout << N << endl;
    for(int i=1; i < N; i++){
        fout << L[i] << ' ';
    }
    fin.close();
    fout.close();
    fout.open("output3.txt");
    ind = 1;
    res = new int *[N];
    int l = 1;
    for(int i = 1; i < N; i++){
        for(int j = 0; j < L[i]; ++j){
            if(i < D[ind]){
                res[l] = new int[2];
                res[l][0] = i;
                res[l][1] = D[ind];
                l++;
            }
            ind++;
        }
    }
    for(int i = 1; i < N; i++){
        cout << res[i][0] << " " << res[i][1] << endl;
    }
    return 0;
}