# include <iostream>
# include <cstdio>
# include <cmath>
# include <algorithm>
#include <stdio.h>
# include <vector>
# include <queue>
using namespace std;
int n,a[500];
bool vis[500];
vector <pair<int, int > > l;
queue <pair <int,int> > l1,l2;
int p1,p2;
int difpos [500][500];
int difst [500][500];
queue <pair <int, int> > q;
int where[500];
vector <pair <int,int> > bypos[500][500];
queue <pair<  int,int> > ans;
struct popcorn
{
    int n;
    int st;
    popcorn *next;
};
popcorn *first = new popcorn;
popcorn *first1 = new popcorn;
void recalculate (int br)
{
  //  cout<<br<<endl;
    if(br==1)return ;
    int mins= 1e9,i,j,f;
    popcorn *u1 = new popcorn;
    popcorn *prev1 = new popcorn;
    popcorn *x1 = new popcorn;

     f = first1->n;
    prev1 = first1;
    u1 = first1->next;

    while(u1->n!=f)
    {//  cout<<prev->n<<" "<<u->n<<endl;
        if(difst[prev1->n][u1->n]<mins){mins = difst[prev1->n][u1->n]; x1 = prev1;  }
        prev1 = u1;
        u1 = u1->next;
     //   cout<<mins<<endl;
    }
 if(difst[prev1->n][u1->n]<mins){mins = difst[prev1->n][u1->n]; x1 = prev1;  }
   // cout<<"kooo"<<mins<<endl;
    //cout<<"make"<<x->n<<" "<<x->next->n<<endl;
    p1=p1+ mins + difpos[x1->n][x1->next->n];
    l1.push({x1->n,x1->next->n});
    swap(x1->st,x1->next->st);
    u1 = x1->next;
    x1->next = x1->next->next;
    if(first1==u1)
    {
        first1 = u1->next;
    }
    delete u1;
    recalculate (br-1);

}
void calculate (int br)
{
  //  cout<<br<<endl;
    if(br==1)return ;
    int mins= 1e9,i,j,f;
    popcorn *u = new popcorn;
    popcorn *prev = new popcorn;
    popcorn *x = new popcorn;

     f = first->n;
    prev = first;
    u = first->next;

    while(u->n!=f)
    {//  cout<<prev->n<<" "<<u->n<<endl;
        if(difpos[prev->n][u->n]<mins){mins = difpos[prev->n][u->n]; x = prev;  }
        prev = u;
        u = u->next;
     //   cout<<mins<<endl;
    }
 if(difpos[prev->n][u->n]<mins){mins = difpos[prev->n][u->n]; x = prev;  }
 p2=p2+ mins + difst[x->n][x->next->n];
   // cout<<"kooo"<<mins<<endl;
    //cout<<"make"<<x->n<<" "<<x->next->n<<endl;
    l2.push({x->n,x->next->n});
    swap(x->st,x->next->st);
    u = x->next;
    x->next = x->next->next;
    if(first==u)
    {
        first = u->next;
    }
    delete u;
    calculate (br-1);

}
void makeswaps()
{
    int i,j,x,br;
    popcorn *u;
    popcorn *u1;
    for(i=1;i<=n;i++)
    {
        if(vis[i]||a[i]==i)continue;
        vis[i]=1;
        x=i;
        j=a[i];
     popcorn *t = new popcorn;
        first->n = x;
        first->st = j;
       t = first;
   popcorn *t1 = new popcorn;
        first1->n = x;
        first1->st = j;
       t1 = first1;


        br=1;
        while(!vis[j])
        {
            u = new popcorn;
            u1 = new popcorn;
            t->next = u;
            t=u;
              t1->next = u1;
            t1=u1;
            vis[j]=1;

            t->n = j;
            t->st = a[j];
            t->next = new popcorn;
                t1->n = j;
            t1->st = a[j];
            t1->next = new popcorn;
            br++;

            j=a[j];
        }
        t->next = first;
        t1->next = first1;
        p1=0;
        p2=0;
        calculate(br);
        recalculate(br);
        //cout<<p1<<" "<<p2<<endl;
        if(p1<=p2)
        {
            while(!l1.empty()){
                l.push_back(l1.front());l1.pop();}
                while(!l2.empty())l2.pop();
        }
        else
            while(!l2.empty()){
                l.push_back(l2.front());l2.pop();}
                while(!l1.empty())l1.pop();
    }
}
void trysolmake(int x, int y)
{
     int mid = 0;
    int mins = difpos[x][y]+difst[a[x]][a[y]];
    int k,st;
    for(k=1;k<=n;k++)
    {
        if(k==x||k==y)continue;
        st  = difpos[x][k]+difst[a[x]][a[k]] + difpos[k][y]+difst[a[x]][a[y]] + difpos[x][k]+difst[a[k]][a[y]];
        if(st<mins){mins = st; mid = k;}
        st  = difpos[y][k]+difst[a[y]][a[k]] + difpos[x][k]+difst[a[x]][a[y]] + difpos[y][k]+difst[a[k]][a[x]];
        if(st<mins){mins = st; mid = k;}
    }
    if(mid==0){
    q.push({x,y});
    swap(a[x],a[y]);
    return ;
    }
    k = mid;
    st  = difpos[x][k]+difst[a[x]][a[k]] + difpos[k][y]+difst[a[x]][a[y]] + difpos[x][k]+difst[a[k]][a[y]];
        if(st==mins)
        {
            q.push({x,k});
            q.push({k,y});
            q.push({x,k});
        swap(a[x],a[y]);
        return ;
        }
     else
     {
         q.push({y,k});
            q.push({k,x});
            q.push({y,k});
        swap(a[x],a[y]);
        return ;
     }
    //return difpos[x][y]+difst[a[x]][a[y]];
}
int trysol(int x, int y)
{
    int mid = 0;
    int mins = difpos[x][y]+difst[a[x]][a[y]];
    int k,st;
    for(k=1;k<=n;k++)
    {
        if(k==x||k==y)continue;
        st  = difpos[x][k]+difst[a[x]][a[k]] + difpos[k][y]+difst[a[x]][a[y]] + difpos[x][k]+difst[a[k]][a[y]];
        if(st<mins){mins = st; mid = k;}
        st  = difpos[y][k]+difst[a[y]][a[k]] + difpos[x][k]+difst[a[x]][a[y]] + difpos[y][k]+difst[a[k]][a[x]];
        if(st<mins){mins = st; mid = k;}
    }
    return mins;
}
void solution()
{
        int i,j,mins=1e9,l,k;
        int o = n;
        for(i=1;i<=n;i++)
        {
            if(a[i]==i){o--;continue;}
            l = trysol(i,a[i]);
            if(mins>l){mins=l;k=i;}
        }
        if(0==o)return ;
        trysolmake(k,a[k]);
        solution();
}
void conc(int x, int y)
{
   // cout<<x<<" "<<y<<endl;
    if(x==y)return ;
    int i;
    for(i=y-1;i>x;i--)
    {
        if(abs(i-a[i])>abs(y-a[i]))
        {
            q.push({i,y});
            swap(a[i],a[y]);
            where[a[i]]=i;
            where[a[y]]=y;
            conc(x,i);
            return ;
        }
    }
    q.push({x,y});
    swap(a[x],a[y]);
    where[a[x]]=x;
    where[a[y]]=y;
    return ;
}
void iftheyare2and0()
{
    int i,j,o=n;
    for(i=1;i<=n;i++)
    {
        if(a[i]==i)continue;
        conc(i,where[i]);
    }
}
void conc22(int x, int y)
{
   // cout<<x<<" "<<y<<endl;
    if(x==y)return ;
    int i;
    for(i=y-1;i>x;i--)
    {
        if(abs(y-a[i])+abs(max(a[x],a[i])-min(a[i],a[y]))-abs(a[x]-a[y])<(abs(i-a[i]))+abs(a[i]-a[a[i]]))
        {
            q.push({i,y});
            swap(a[i],a[y]);
            where[a[i]]=i;
            where[a[y]]=y;
            conc(x,i);
            return ;
        }
    }
    q.push({x,y});
    swap(a[x],a[y]);
    where[a[x]]=x;
    where[a[y]]=y;
    return ;
}
void iftheyare2and2()
{
    int i,j,o=n;
    for(i=1;i<=n;i++)
    {
        if(a[i]==i)continue;
        conc22(i,where[i]);
    }
}
void make_floid()
{
    int k,i,j,w;
    for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (difpos[i][j] > (difpos[i][k] + difpos[k][j]+difpos[i][k]))
{
    difpos[i][j] = difpos[i][k] + difpos[k][j] + difpos[i][k];
    bypos[i][j].clear();
    for(w=0;w<bypos[i][k].size();w++)
    {
        bypos[i][j].push_back(bypos[i][k][w]);
    }
     for(w=0;w<bypos[k][j].size();w++)
    {
        bypos[i][j].push_back(bypos[k][j][w]);
    }
     for(w=0;w<bypos[i][k].size();w++)
    {
        bypos[i][j].push_back(bypos[i][k][w]);
    }
   // cout<<i<<" "<<j<<" "<<bypos[i][j].size()<<endl;
}

for (i = 0; i < n; i++)
difpos[i][i] = 0;
}
int main()
{

    freopen ("sorting.in","r",stdin);
freopen ("sorting.out","w",stdout);
    cin>>n;
    int i;
    for(i=1;i<=n;i++)

        {cin>>a[i];
        where[a[i]]=i;
        }
          int o,j;
       cin>>o;
         for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                  cin>>difpos[i][j];
                 bypos[i][j].push_back({i,j});
            }
                int k;
        cin>>k;
if((o==4&&k==0)||(o==4&&k>=3))
   {
       makeswaps();
         {
                cout<<l.size()<<endl;
        for(i=0;i<l.size();i++)
            cout<<l[i].first<<" "<<l[i].second<<endl;

            return 0;
           }
   }

          for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            cin>>difst[i][j];

          if(o==2&&k==0)iftheyare2and0();
           else{
          if(o==1&&k==0)make_floid();
       solution();}

      //iftheyare2and2();
        //cout<<q.size()<<endl;
        int x,y,w;
       // if((o==4&&k==3))

       while(!q.empty())
        {
          // cout<<q.front().first<<" "<<q.front().second<<endl;
          x=q.front().first;
          y=q.front().second;
         // cout<<bypos[x][y].size()<<endl;
          for(w=0;w<bypos[x][y].size();w++)
          {
              ans.push({bypos[x][y][w].first,bypos[x][y][w].second});
          }
            q.pop();

        }
        cout<<ans.size()<<endl;
        while(!ans.empty())
        {
            cout<<ans.front().first<<" "<<ans.front().second<<endl;
            ans.pop();
        }
        return 0;
}