using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace locopt
{
    class Lab
    {
        int n;
        int[,] Way;
        List<int> d = new List<int>();
        public Lab()
        {
            StreamReader Sr = new StreamReader("salesmanopt.in");
            n = int.Parse(Sr.ReadLine());
            Way = new int[n, n];
            for (int i = 0; i < n; i++)
            {
                string[] line = Sr.ReadLine().Split(" ".ToArray(), StringSplitOptions.RemoveEmptyEntries);
                for (int j = 0; j < n; j++)
                {
                    Way[i, j] = int.Parse(line[j]);
                }
            }
            d = new List<int>();
            GetBestWay();
        }
        void swap(int i, int j)
        {
            int c = d[i];
            d[i] = d[j];
            d[j] = c;
        }
        private void GetBestWay()
        {
            bool[] isgood = new bool[n];
            isgood[0] = false;
            for (int hg = 1; hg < n; hg++) { isgood[hg] = true; }
            d.Add(0);
            while (d.Count != n)
            {
                double Min = int.MaxValue;
                int min = 0;
                int k = d[d.Count - 1];
                for (int i = 0; i < n; i++)
                {
                    if (Way[k, i] < Min && k != i && isgood[i] == true)
                    {
                        min = i;
                        Min = Way[k, i];
                    }
                }
                d.Add(min);
                isgood[min] = false;
            }
            Sic();
        }

        private void Sic()
        {
            StreamWriter sw = new StreamWriter("salesmanopt.out");
            string r = "";
            for (int p = 0; p < n; p++)
            {
                r += d[p].ToString();
                if (p != n - 1)
                {
                    r += " ";
                }
            }
            sw.WriteLine(r);
            while (true)
            {
                bool good = false;
                for (int i = 1; i < n; i++)
                {
                    for (int j = i + 1; j < n; j++)
                        if (j == i + 1)
                        {
                            if (checkFirst(i, j) == true)
                            {
                                string r1 = i.ToString() + " " + j.ToString();
                                sw.WriteLine(r1);
                                swap(i, j);
                                good = true;
                                break;
                            }
                        }
                        else
                        {
                            if (checkSecond(i, j) == true)
                            {
                                string r2 = i.ToString() + " " + j.ToString();
                                sw.WriteLine(r2);
                                swap(i, j);
                                good = true;
                                break;
                            }
                        }
                    if (good == true) break;
                }
                if (good == false) break;
            }
            sw.WriteLine("optimal");
            sw.Close();
        }
        private bool checkFirst(int i, int j)
        {
            if (Way[d[i - 1], d[i]] + Way[d[i], d[j]] + Way[d[j], d[(j + 1) % n]] >
                                Way[d[i - 1], d[j]] + Way[d[j], d[i]] + Way[d[i], d[(j + 1) % n]])
            {
                return true;
            }
            else return false;
        }
        private bool checkSecond(int i, int j)
        {
            if (Way[d[i - 1], d[i]] + Way[d[i], d[i + 1]] + Way[d[j - 1], d[j]] + Way[d[j], d[(j + 1) % n]] >
                                Way[d[i - 1], d[j]] + Way[d[j], d[i + 1]] + Way[d[j - 1], d[i]] + Way[d[i], d[(j + 1) % n]])
            {
                return true;
            }
            else return false;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Lab x = new Lab();
        }
    }
}