#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple

struct union_find{
    ll N;
    vi par, sz;
    union_find(ll n): N(n){
        par.resize(N);
        sz.resize(N,1);
        rep(i,0,N) par[i] = i;
    }
    ll root(ll now){
        if(par[now] == now) return now;
        return par[now] = root(par[now]);
    }
    void merge(ll u, ll v){
        u = root(u);
        v = root(v);
        if(u == v) return;
        if(sz[u] > sz[v]) std::swap(u,v);
        sz[v] += sz[u];
        sz[u] = 0;
        par[u] = v;
    }
    bool same(ll u, ll v){
        return root(u) == root(v);
    }
};


int main(){
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    ll N,M; cin >> N >> M;
    vector<vii> data(N,vii(M));
    vi A(N*M);
    rep(i,0,N*M){
        cin >> A[i];
        A[i]--;
        data[i/M][A[i]].pb(i);
    }
    vii edge(N+M), weight(N+M);
    {
        ll cnt = N*M;
        rep(i,0,N){
            rep(j,0,M){
                if(data[i][j].size() == 0){
                    edge[j].pb(M+i);
                    weight[j].pb(cnt++);
                }
                else{
                    rep(k,1,data[i][j].size()){
                        edge[M+i].pb(j);
                        weight[M+i].pb(data[i][j][k]);
                    }
                }
            }
        }
    }
    ll ans = 0;
    {
        vector<bool> flag(N+M);
        rep(i,0,N+M){
            if(edge[i].empty()) continue;
            if(flag[i]) continue;
            flag[i] = true;
            std::queue<ll> que;
            que.push(i);
            ll sum = 0;
            while(!que.empty()){
                ll now = que.front();
                que.pop();
                sum += edge[now].size();
                for(auto next: edge[now]){
                    if(flag[next]) continue;
                    flag[next] = true;
                    que.push(next);
                }
            }
            sum /= 2;
            ans += sum+1;
        }
        cout << ans << ln;
    }
    
    union_find tree(N*M*2);
    vi nidx(N+M);
    vi next(2*N*M, -1);
    rep(i,0,N+M){
        if(nidx[i] == edge[i].size()) continue;
        ll now = i;
        vi ord;
        while(true){
            if(nidx[now] == edge[now].size()) break;
            ll next = edge[now][nidx[now]];
            ll vert = weight[now][nidx[now]];
            ord.pb(vert);
            nidx[now]++;
            now = next;
        }
        rep(j,0,ord.size()){
            next[ord[j]] = ord[(j+1)%ord.size()];
            tree.merge(ord[j], ord[0]);
        }
        assert(nidx[i] == edge[i].size());
    }

    rep(i,0,M+N){
        rep(j,0,weight[i].size()){
            ll n = weight[i][0];
            ll m = weight[i][j];
            if(tree.same(n,m)) continue;
            tree.merge(n,m);
            std::swap(next[n], next[m]);
        }
    }
    ll cnt = 0;
    A.pb(-1);
    rep(i,0,2*N*M){
        if(next[i] == -1) continue;
        vi ord;
        ll now = i;
        while(true){
            if(next[now] == -1) break;
            if(now < N*M) ord.pb(now);
            ll nex = next[now];
            next[now] = -1;
            now = nex;
        }
        ll n = ord.size();
        cout << ord[n-1]+1 << " " << N*M+1 << ln;
        assert(A[N*M] == -1);
        std::swap(A[N*M], A[ord[n-1]]);
        cnt++;
        per(j,n-1,1){
            cout << ord[j-1]+1 << " " << ord[j]+1 << ln;
            assert(A[ord[j]] == -1);
            std::swap(A[ord[j]], A[ord[j-1]]);
            cnt++;
        }
        cout << N*M+1 << " " << ord[0]+1 << ln;
        assert(A[ord[0]] == -1);
        std::swap(A[ord[0]], A[N*M]);
        cnt++;
    }
return 0;
    assert(cnt == ans);
    cout << endl;
    rep(i,0,N){
        vi cnt(M);
        rep(j,i*M,i*M+M) cnt[A[j]]++;
        rep(j,0,M) assert(cnt[j] == 1);
    }
}