#include <bits/stdc++.h>
using namespace std;

vector<int> p;

int dsu_get (int v) {
	return (v == p[v]) ? v : (p[v] = dsu_get (p[v]));
}

void dsu_unite (int a, int b) {
	a = dsu_get (a);
	b = dsu_get (b);
	if (rand() & 1)
		swap (a, b);
	if (a != b)
		p[a] = b;
}

struct rebro{
    int v, f, t;
};

vector<vector<int> > G;
vector<rebro> rs;
vector<int> ans;
bool Seen[160001]={0}, Seenv[401]={0};

void dfs(int v, int pos){
    if (Seenv[v]){
        return;
    }
    for (auto x: G[v]){
        if (!Seen[x]){
            Seen[x]=true;
            ans.insert(ans.begin()+pos, rs[x].v);
            dfs(rs[x].t, pos+1);
        }
    }
    Seenv[v]=true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int n,m,x, ind;
	cin>>n>>m;
    G.resize(m+1);
    p.resize(m+1);
    for (int i=1; i<=m; ++i){
        p[i]=i;
    }
    int nofr=0;
    for (int i=0; i<n; ++i){
        bool was[m+1]={0};
        vector<pair<int,int> > povt;
        for (int j=0; j<m; ++j){
            cin>>x;
            if (was[x]){
                povt.push_back({x, m*i+j+1});
            }
            else{
                was[x]=true;
            }
        }
        ind=0;
        for (int i=1; i<=m; ++i){
            if (!was[i]){
                rs.push_back({povt[ind].second, i, povt[ind].first});
                G[i].push_back(nofr++);
                dsu_unite(i, povt[ind].first);
                ++ind;
            }
        }
    }
    int comps[m+1]={0};
    for (int i=1; i<=m; ++i){
        comps[dsu_get(i)]+=G[i].size();
    }
    int nofc=0, tobeg=-1;
    for (int i=1; i<=m; ++i){
        if (comps[i]>1){
            tobeg=i;
            nofc+=comps[i]+1;
        }
    }
    cout<<nofc<<'\n';
    if (tobeg==-1){
        return 0;
    }
    for (int i=1; i<=m; ++i){
        dfs(i, 0);
    }
    cout<<ans[ans.size()-1]<<' '<<n*m+1<<'\n';
    for (int i=ans.size()-2; i>=0; --i){
        cout<<ans[i]<<' '<<ans[i+1]<<'\n';
    }
    cout<<n*m+1<<' '<<ans[0];
    return 0;
}
