#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <set>
#include <cstdlib>
#include <time.h>
using namespace std;

int n;

int p[411];
int distPos[411][411];
int distVal[411][411];
int posType,valType;
int where[411];

int cost = 0;

vector< pair<int,int> > ans;

int ABS(int a)
{
    if (a < 0)
        return -a;
    else
        return a;
}

int MIN(int a,int b)
{
    if (a < b)
        return a;
    else
        return b;
}

int MAX(int a,int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int swapCost(int L,int R)
{
    return distPos[L][R] + distVal[ p[L] ][ p[R] ];
}

void doSwap(int L,int R)
{
    where[ p[L] ] = R;
    where[ p[R] ] = L;

    int swp = p[L];
    p[L] = p[R];
    p[R] = swp;
}

int dist[411];
bool taken[411];
int cf[411];

int getCost(int x1,int x2,int A,int B)
{
    if (x2 == B)
        return distPos[x1][x2] + distVal[ p[A] ][ p[B] ];
    else
        return distPos[x1][x2]*2 + distVal[ p[A] ][ p[x1] ] + distVal[ p[B] ][ p[x2] ];
}

int getCostSimple(int x1,int x2,int A,int B)
{
    return distPos[x1][x2] + distVal[A][ p[x2] ];
}

int lb[411];

void cover(int ver,int l)
{
    if (lb[ver] != -1)
        return;

    lb[ver] = l;
    cover(p[ver],l);
}

int getSwaps()
{
    int i;
    int ans = 0;

    for (i=1;i<=n;i++)
    {
        lb[i] = -1;
    }
    for (i=1;i<=n;i++)
    {
        if (lb[i] == -1)
        {
            ans++;
            cover(i, i);
        }
    }

    return ans;
}

int viable(vector<int> ops)
{
    int i;
    int preans = getSwaps();

    for (i=1;i<ops.size();i++)
    {
        doSwap(ops[i-1], ops[i]);
    }

    int postans = getSwaps();

    for (i=(int)ops.size()-1;i>=1;i--)
    {
        doSwap(ops[i-1], ops[i]);
    }
    return postans - preans;
}

vector<int> seq;
vector<int> seq2;

int labels[411];

int cleanSwap(int A,int B,bool real)
{
    int i,j;
    int cost1, cost2;

    ///First pass
    for (i=1;i<=n;i++)
    {
        dist[i] = -1;
        taken[i] = false;
    }

    dist[A] = 0;
    cf[A] = 0;

    for (i=1;i<=n;i++)
    {
        int minVer = -1;
        for (j=1;j<=n;j++)
        {
            if (taken[j])
                continue;
            if (dist[j] == -1)
                continue;

            if (minVer == -1)
                minVer = j;
            else if (dist[minVer] > dist[j])
                minVer = j;
        }

        taken[minVer] = true;

        if (minVer == B)
            break;

        for (j=1;j<=n;j++)
        {
            int newCost = getCost(minVer, j, A, B);

            if (newCost + dist[minVer] < dist[j] || dist[j] == -1)
            {
                dist[j] = newCost + dist[minVer];
                cf[j] = minVer;
            }
        }
    }

    cost1 = dist[B];

    seq.clear();
    int cur = B;

    while(cur != 0)
    {
        seq.push_back(cur);
        cur = cf[cur];
    }

    reverse(seq.begin(), seq.end());

    ///Second pass
    for (i=1;i<=n;i++)
    {
        dist[i] = -1;
        taken[i] = false;
    }

    dist[A] = 0;
    cf[A] = 0;

    for (i=1;i<=n;i++)
    {
        int minVer = -1;
        for (j=1;j<=n;j++)
        {
            if (taken[j])
                continue;
            if (dist[j] == -1)
                continue;

            if (minVer == -1)
                minVer = j;
            else if (dist[minVer] > dist[j])
                minVer = j;
        }

        taken[minVer] = true;

        if (minVer == B)
            break;

        for (j=1;j<=n;j++)
        {
            int newCost = getCostSimple(minVer, j, A, B);

            if (p[j] == j)
                continue;

            //if (labels[A] != labels[j])
            //    continue;

            if (newCost + dist[minVer] < dist[j] || dist[j] == -1)
            {
                dist[j] = newCost + dist[minVer];
                cf[j] = minVer;
            }
        }
    }

    cost2 = dist[B];

    seq2.clear();
    cur = B;

    while(cur != 0)
    {
        seq2.push_back(cur);
        cur = cf[cur];
    }

    reverse(seq2.begin(), seq2.end());

    int viability = viable(seq2);

    if (viability <= 0)
        cost2 = 999999999;
    else
        cost2 /= viability;

    if (real)
    {
        if (cost2 < cost1)
        {
            seq = seq2;
            for (i=1;i<seq.size();i++)
            {
                cost += swapCost(seq[i-1], seq[i]);
                doSwap(seq[i-1],seq[i]);
                ans.push_back(make_pair(seq[i-1],seq[i]));
            }
        }
        else
        {
            //fprintf(stderr,"One(or 2) fixes for %d with length %d\n",cost1,seq.size());
            for (i=1;i<seq.size();i++)
            {
                cost += swapCost(seq[i-1],seq[i]);
                doSwap(seq[i-1],seq[i]);
                ans.push_back(make_pair(seq[i-1],seq[i]));
            }

            for (i=(int)seq.size()-2;i>=1;i--)
            {
                cost += swapCost(seq[i-1],seq[i]);
                doSwap(seq[i-1],seq[i]);
                ans.push_back(make_pair(seq[i-1],seq[i]));
            }
        }
    }

    if (real)
    {
        //fprintf(stderr,"Operation cost = %d\n",MIN(cost1,cost2));
    }

    if (cost2 < cost1)
        return cost2;
    else
        return cost1;
}

vector<int> cycleList;

int putLabel(int ver,int label)
{
    if (labels[ver] != -1)
        return 0;

    cycleList.push_back(ver);

    labels[ver] = label;
    return 1 + putLabel(p[ver], label);
}

vector< pair<int,int> > options;

const int LIMIT = 1;

vector< pair<int,int> > bestLocalAns;
vector< pair<int,int> > localAns;
int bestcost = -1;

int bruteLabel[411];

int putSimpleLabels(vector<int> vers)
{
    int i;
    int ctr = 0;

    for (i=0;i<vers.size();i++)
    {
        bruteLabel[ vers[i] ] = -1;
    }

    for (i=0;i<vers.size();i++)
    {
        int cur = vers[i];

        if (bruteLabel[cur] == -1)
            ctr++;

        while (bruteLabel[cur] == -1)
        {
            bruteLabel[cur] = vers[i];
            cur = p[cur];
        }
    }

    return ctr;
}

int cutDown = 3;

void batrak(vector<int> cycle, int curcost)
{
    if (bestcost != -1 && curcost >= bestcost)
        return;

    int i,j;
    vector< pair< int, pair<int,int> > > ops;
    vector<int> allCosts;
    int groups;
    int optimistic = 0;

    /*for (i=0;i<cycle.size();i++)
    {
        cout<<cycle[i]<<" ";
    }
    cout<<endl;*/

    groups = putSimpleLabels(cycle);

    for (i=0;i<cycle.size();i++)
    {
        for (j=i+1;j<cycle.size();j++)
        {
            if (bruteLabel[ cycle[i] ] == bruteLabel[ cycle[j] ])
            {
                allCosts.push_back(swapCost(cycle[i], cycle[j]));
                ops.push_back(make_pair(swapCost(cycle[i],cycle[j]), make_pair(i,j)));
            }
        }
    }

    if (ops.empty()) ///Done
    {
        bestcost = curcost;

        bestLocalAns.clear();

        for (i=0;i<localAns.size();i++)
        {
            bestLocalAns.push_back(localAns[i]);
        }

        return;
    }

    sort(allCosts.begin(), allCosts.end());

    optimistic = curcost;
    for (i=0;i<(int)cycle.size() - groups;i++)
    {
        optimistic += allCosts[i];
    }

    if (optimistic >= bestcost && bestcost != -1)
    {
        //cerr<<"Optimistic is "<<optimistic<<" while best is "<<bestcost<<endl;
        return;
    }
    /*cout<<"Got options"<<endl;
    for (i=0;i<ops.size();i++)
    {
        cout<<ops[i].second.first<<"<->"<<ops[i].second.second<<endl;
    }*/
    sort(ops.begin(), ops.end());

    if (ops.size() > cutDown)
        ops.resize(cutDown);

    for (i=0;i<ops.size();i++)
    {
        int ind1 = ops[i].second.first;
        int ind2 = ops[i].second.second;
        int cst = ops[i].first;

        //cout<<"testing "<<ind1<<","<<ind2<<endl;

        doSwap(cycle[ind1], cycle[ind2]);
        localAns.push_back(make_pair(cycle[ind1], cycle[ind2]));

        batrak(cycle, curcost + cst);

        doSwap(cycle[ind1], cycle[ind2]);
        localAns.pop_back();
    }

    return;
}

void bruteforceSubcycle(vector<int> inds)
{
    int i;
    int localCost = 0;

    //fprintf(stderr,"Bruteforcing\n");

    /*for (i=0;i<inds.size();i++)
    {
        cout<<inds[i]<<" == "<<p[ inds[i] ]<<endl;
    }*/

    bestcost = -1;
    bestLocalAns.clear();

    batrak(inds, 0);

    //cerr<<"Got "<<bestcost<<endl;

    //cout<<"done"<<endl;
    for (i=0;i<bestLocalAns.size();i++)
    {
        int ind1 = bestLocalAns[i].first;
        int ind2 = bestLocalAns[i].second;
        //cout<<"swap "<<ind1<<","<<ind2<<endl;

        localCost += swapCost(ind1, ind2);
        cost += swapCost(ind1, ind2);
        doSwap(ind1, ind2);
        ans.push_back(make_pair(ind1, ind2));
    }

    for (i=0;i<inds.size();i++)
    {
        if (p[ inds[i] ] != inds[i])
        {
            fprintf(stderr,"BAD THING\n");
            while(1);
        }
    }

    //fprintf(stderr,"@@@@@@@@@@@@@@@@@@@@@@@@@@ Bruteforce gives average of %d\n",localCost/(int)bestLocalAns.size());

    return;
}

int whereIs(int ver)
{
    int i;

    for (i=1;i<=n;i++)
    {
        if (p[i] == ver)
            return i;
    }

    return -1;
}

bool loopToFind(int v,int bad,int good)
{
    if (v == bad)
        return false;
    else if (v == good)
        return true;
    else
        return loopToFind(p[v], bad, good);
}

const int THRESHOLD = 15;

pair<int,int> getTwoVals(int x)
{
    return make_pair(swapCost(x,p[x]), swapCost(where[x], x));
}

pair< pair<int,int>, pair<int,int> > getFourVals(int x,int y)
{
    pair<int,int> v1 = getTwoVals(x);
    pair<int,int> v2 = getTwoVals(y);

    return make_pair(v1,v2);
}

int parseQuadruple(pair< pair<int,int>, pair<int,int> > quad)
{
    int minval = MIN(quad.first.first, quad.first.second);
    minval = MIN(minval, quad.second.first);
    minval = MIN(minval, quad.second.second);

    return quad.first.first + quad.first.second + quad.second.first + quad.second.second - minval;
}

int main()
{
    freopen("sorting.in","r",stdin);
    freopen("sorting.out","w",stdout);

    int i,j,in;
    int swp;
    int components;

    srand(1337);

    scanf("%d",&n);

    for (i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        where[ p[i] ] = i;
    }

    scanf("%d",&posType);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            scanf("%d",&distPos[i][j]);
        }
    }
    ///3(+2) 5(+3) 4(+1) 1(-3) 2(-3)
    scanf("%d",&valType);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            scanf("%d",&distVal[i][j]);
        }
    }

    if (posType == 2 && valType == 0)
    {
        int estimate = 0;

        for (i=1;i<=n;i++)
        {
            estimate += ABS(p[i] - i);
        }
        estimate /= 2;

        fprintf(stderr,"ANSWER SHOULD BE %d\n",estimate*6);

        bool progress = true;
        while(progress)
        {
            progress = false;
            for (i=1;i<=n;i++)
            {
                int goalA = p[i] - i;

                if (goalA <= 0)
                    continue;

                for (j=i+1;j<=n;j++)
                {
                    int goalB = p[j] - j;

                    if (goalB >= 0)
                        continue;

                    if (goalA >= j-i && goalB <= i-j)
                    {
                        cost += swapCost(i,j);
                        doSwap(i,j);
                        ans.push_back(make_pair(i,j));
                        progress = true;

                        break;
                    }
                }
            }
        }
    }
    else if (posType == 3 && valType == 0 && false)
    {
        bool progress = true;
        int bestx, besty;
        double perBalanceBest;

        while(progress)
        {
            progress = false;

            perBalanceBest = -99999999.0;
            for (i=1;i<=n;i++)
            {
                int goalA = p[i] - i;

                for (j=i+1;j<=n;j++)
                {
                    int goalB = p[j] - j;
                    int balance = ABS(goalA) + ABS(goalB);
                    int newBalance = ABS(p[i] - j) + ABS(p[j] - i);
                    double previousCost = sqrt((double)balance);
                    double newCost = sqrt((double)newBalance);
                    double costImprovement = previousCost - newCost;

                    if (costImprovement <= 0.0)
                        continue;
                    if (balance - newBalance <= 0)
                        continue;

                    //fprintf(stderr,"%d\n",balance - newBalance);
                    double effectiveWin = costImprovement - (double)swapCost(i,j);

                    if (effectiveWin > perBalanceBest)
                    {
                        perBalanceBest = effectiveWin;
                        bestx = i;
                        besty = j;
                        progress = true;
                    }
                }
            }

            if (progress)
            {
                cost += swapCost(bestx, besty);
                doSwap(bestx, besty);
                ans.push_back(make_pair(bestx, besty));

                fprintf(stderr,"%d\n",ans.size());
            }
        }
    }
    else if (false)
    {
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++)
            {
                if (p[j] != j)
                {
                    cost += swapCost(j,p[j]);
                    doSwap(j,p[j]);
                    ans.push_back(make_pair(j,p[j]));
                }
            }
        }
    }
    else if ( (posType == 4 && valType == 4) || (posType == 4 && valType == 0) )
    {
        for (i=n;i>=1;i--)
        {
            if (i != p[i])
            {
                cost += swapCost(where[i], i);
                ans.push_back(make_pair(where[i], i));
                doSwap(where[i], i);
            }
        }
    }
    else if (posType != 1 || valType != 0)
    {
        double thebestcost = -999999999.0;
        int x,y;

        for (double coef = -1.0; coef <=3.1 ; coef += 1.3)
        {
            if ((double)clock() / (double)CLOCKS_PER_SEC > 2.3)
                break;

            int remcost = cost;
            vector< pair<int,int> > remans;

            for (i=0;i<ans.size();i++)
            {
                remans.push_back(ans[i]);
            }
            cost = 0;
            ans.clear();

            for (i=1;i<=n;i++)
            {
                thebestcost = -999999999.0;

                memset(labels,-1,sizeof(labels));

                for (j=1;j<=n;j++)
                {
                    int cur = j;

                    while(labels[cur] == -1)
                    {
                        labels[cur] = j;
                        cur = p[cur];
                    }
                }

                for (j=1;j<=n;j++)
                {
                    for (in=j+1;in<=n;in++)
                    {
                        if (labels[j] != labels[in])
                            continue;

                        int i1 = j;
                        int i2 = in;
                        pair< pair<int,int>, pair<int,int> > prev = getFourVals(j, in);

                        doSwap(i1, i2);

                        pair< pair<int,int>, pair<int,int> > post = getFourVals(j, in);

                        doSwap(i1, i2);

                        int prevVal = parseQuadruple(prev);
                        int postVal = parseQuadruple(post);

                        double c = (double)swapCost(i1, i2)*coef + (double)postVal - (double)prevVal;
                        //int c = swapCost(i1, i2);

                        if (thebestcost < -999999998.0 || c < thebestcost)
                        {
                            thebestcost = c;
                            x = j;
                            y = in;
                        }
                    }
                    /*if (j != p[j])
                    {
                        int i1 = j;
                        int i2 = p[j];
                        int prev = swapCost(p[j], p[ p[j] ]) + swapCost(whereIs(j), j);
                        int c = swapCost(i1, i2);

                        doSwap(i1, i2);

                        int post = swapCost(j, p[j]) + swapCost(whereIs(j), j);

                        doSwap(i1, i2);

                        c += (post-prev);

                        if (thebestcost == -1 || c < thebestcost)
                        {
                            thebestcost = c;
                            x = j;
                            y = p[j];
                        }
                    }*/
                }

                if (thebestcost > -999999998.0)
                {
                    cost += swapCost(x,y);
                    //fprintf(stderr,"Step %d = %d\n",i,swapCost(x,y));
                    doSwap(x,y);
                    ans.push_back(make_pair(x,y));
                }
                else
                    break;
            }

            for (i=(int)ans.size()-1;i>=0;i--)
            {
                doSwap(ans[i].first,ans[i].second);
            }

            if (remcost < cost && remcost != 0)
            {
                ans.clear();
                cost = remcost;

                for (i=0;i<remans.size();i++)
                {
                    ans.push_back(remans[i]);
                }
            }
        }

        for (i=0;i<ans.size();i++)
        {
            doSwap(ans[i].first,ans[i].second);
        }
    }
    else
    {
        for (i=n;i>=1;i--)
        {
            for (j=1;j<=n;j++)
            {
                labels[j] = -1;
            }

            bool bruteforced = false;
            vector<int> comps;
            components = 0;
            for (j=1;j<=n;j++)
            {
                if (labels[j] == -1)
                {
                    components++;
                    cycleList.clear();
                    comps.push_back( putLabel(j, j) );

                    if (comps.back() <= THRESHOLD && comps.back() > 1 && false)
                    {
                        bruteforceSubcycle(cycleList);
                        bruteforced = true;
                    }
                }
            }

            if (bruteforced)
            {
                i--;
                continue;
            }

            //fprintf(stderr,"Components = %d\n",components);

            options.clear();

            for (j=1;j<=n;j++)
            {
                for (in=1;in<=n;in++)
                {
                    if (j != in && labels[j] == labels[in])
                    {
                        if (j == p[in] || in == p[j])
                        options.push_back(make_pair(j, in));
                    }
                }
            }

            random_shuffle(options.begin(),options.end());
            random_shuffle(options.begin(),options.end());

            if (options.size() > LIMIT)
                options.resize(LIMIT);

            int op1 = -1, op2 = -1;
            int bestv = 999999999;
            for (j=0;j<options.size();j++)
            {
                int v = cleanSwap(options[j].first, options[j].second, false);

                if (v < bestv)
                {
                    bestv = v;
                    op1 = options[j].first;
                    op2 = options[j].second;
                }

                v = cleanSwap(options[j].second, options[j].first, false);

                if (v < bestv)
                {
                    bestv = v;
                    op1 = options[j].second;
                    op2 = options[j].first;
                }
            }

            if (op1 == -1)
                break;

            //fprintf(stderr,"%d %d\n",op1,op2);

            cleanSwap(op1, op2, true);
        }
    }

    for (i=1;i<n;i++)
    {
        if (p[i] > p[i+1])
        {
            fprintf(stderr, "NOT SORTED\n");
            return 0;
        }
    }

    printf("%d\n",(int)ans.size());

    for (i=0;i<ans.size();i++)
    {
        printf("%d %d\n",ans[i].first,ans[i].second);
    }

    fprintf(stderr,"Cost = %d\n",cost);
    fprintf(stderr,"Average cost per operation = %d\n",cost/(int)ans.size());
    fprintf(stderr,"Total operations = %d\n",ans.size());
    return 0;
}