Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Accepted

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAJ3vbF0C/+19e3xUxfX43c1reWWD9RERZdEooBCyJECCCglh4S5sAEnAFB+XzWaXrO6ru3dDoqDYBOu6RPlaa20/bb/82m+t7ddWf7W1+IJEHsE3viiKIlrUXSMaXxBF2N85M3M3c+/ujdD29/3+4yqZPeeeM3POmTNnzsy9O/dmm2O+0WAQlI9RmC0gdMXYagJXM/y9kTQJ4CqFYfB3nDBWyAc4j6OrFqpV5QCrWilNjC4H/uXCv0ojhSuN1apyLKNTSgNX5gn8p1pVbnQKqlIQLGk+lHWfn2L3+VepSksuxZcVqPmMjG+A8Q0weqUUjIKqVPTLZf8aGL6B6aWU8xjdPI4eP0vfk5vxe9tVFG67qlpVbmR0GzV8VwBfvnDynyJWLmPt6dllIpNfKZV+mOrzNs2omOprnuLzBqJtU9oqZ0yZUVEaCZZOIzIVMdoFi5er7FjMZD6d+QBe//VBq+i65N1RO7ffdOLOsX/7qqF965l47VLGh12yIVDUkjt+mNEgVAjroWq8Nhv+1cK/P79Z/trwWzZJv3Q9ufMOf2r3bRtcZ75av7lj4/erP53yqXRtoaW1bKLtNUf3hxd1n37vyNpfjQ1tabdf/8hQ9jkEApyWBf+KMTt+qiE7/s9CdnxR2sPUn3E6+BfzstezTgc/Kj87/lkdebp06rlGp54CHbxPB/+j3Ox4r067l+rUU6lj/7/q4Cfo1FOuY+fVOvXcpFPPZzr0FTr0S3Ta/bFOv+Tp+FWDTruP6dCfoyPPKh36Zh36IzrjYrxOPffp9PujOvjHdOq/Scc+Xh17ijryT9HBt+vY83wd+j/p6OvXkX+FTj0f6ehVpVPPAR27yTr4Z3Tk/Fhn3E3QscPLOvW/oCPnEh19n9Rp9wKoZ7wwRngoTOedYoY/jeH7I6tU89aEPIoXZIpvZPgRuQzP6lnP8L9l7VrGVKvaXcDs06/BL4J2R0M9B1n9io/dkEvxQnSVaj583UDbXR9W05uZPbvPVte/NI/WszmsrudyVv9Bhi9iFxYwvVbJGr2Y/TedU60JxN6miNzsuuQSnJNnCJK02h8MSBHZGZYlSZAWtkrL3Ku9EdkdrvU5IxF3RJDsDXVSszvM0A11tb5gwN3gbPK56bXsV6SQ3BJ2O5ul693tkgu+yYh0tTklT9jtltxtLndI9gYDgrRycX2kApoNWcskbCkih4PttmWL6p12l41cDlbBBW8g4g7Ldp/Ntqw+2CDhhUX18nSX3B5yA6G1HGjWeJvdAaD0yrZWIKiXrTMlCeQIrpGaQBSnzxd0tVLOiLXc4w00Sx5vOCJLQY9t6SKX30+bm+7xRSMtShUz+CpczohMaoAL5eFoQPb6QZlwOBieZ+UYgqCE2+lXhHYB1upqcYYlOez0yhGQF7SAGpqcEa9LobY3SA1lkq1+hrR0UX255GP2Io2TmqvAyn5vAExJRYjUWtFOESJ3QwNUWDVYoTewmlWbpXViW2pcudIbjIBuEXeFHQzH1AD8DDCW0+ceRGgUZo2nJQED8p2GKL8KIzPpoL2sFpnu8rmdYRtcmSbZQSb4JxO3AdWnlSm9EIxid0lhZ2C1G5pUenMG6U3wWVkKBNUdipdncp2tud5gB8l4f0SERlfWFU3g6gHwAdnVwvktyFYvuf0huR3GQggGUzDsXO22MQ+1Tqda0y5pinr0+6McaNDY0uq2NinkDkeCAafPC9W2ljEDpsWcN431SgSMVSeB4a6XoMZmBTvDGQq5A81EScA0+5a2QlfIVaA7saKMeq44JelIP1S4wP6ZvOBmOrzIFljjJ8wzWeuc7arAdDQ62Px+lbOk3ZKqSuxPBjDQasJHsDwUlW0u5qWnNgbAS7G3icMtAZP5g81uot9iCEfQaJuzydtqRfeLeCUXxkQJIw6MbE/QxgcvK2jCxqePKZ1hcSCeGXZDSGgFdbONvlo22BbxfV2xpsUpazuWDT3sWAzqfhrP4dtqF/QIQlZBWh5Yg26/zB2J+t140UXJPEGoA2yKER4Cv8fp9QlgKDnoEzzuoEfwrHbLEcFFzI0XfISa9IDsbvPKgt/td/lDpAi1Cx6XLxhxC35KD0h/sBWjPTbI5ha/0xsQMPILC2prpfLSMmGBwz63VppWaq1If51WOl2obWysmWuXrKXlFN3YCNQVpVarCqziIbIexP9y2JrSCGvJPPIX/6Mw/Suw77lpHvyew64bYS1qJOvRXEaVz+jz2fUCVpo4+sz/8mHeNggH8wbXc0svah+BK9aOfGW9bBSOs+tl8O/u/7gnH3cJ4vkUFx3jHYZS3JOmzyW5gJLnvPLg9Xm4cv41o3cO/NSIOyB/ZHDs5klGXEk/wWB50l0m1PgZVt9AkOYL+dp9E5Zf5LF1tPJZz+FrOfxmDm/j8A9x+Es5/EEOP5/DK3kc4i9TJbCD+Mv59QmHX8DXz+Fr+Hqig/i5HLo4RPEFXK5F8jQOb+TwEzl8Docv4/C5/LqUw/N2rubwBfz6hMOb+LyQww/j8I0cfjhvHw4/gsO3cPiRHD7E4Udx+DYOX8j7A4c3c/jbOHwRh9/E4Udz+Hs5PJ//b+bw3+Pw93P403l/4/DzOPwWDn8mh+/m8Gdx+N0cvpjD7+HwZ3P4fRz+HN4POfwcDp/g8GN5/+fw53L4AQ5/Hu/PPxjEj+PQJg7Pr3+LOPx43v85/Pm8/3P4C3j/5/AlvP9z+At5/+fwF/H+z+En8P7P4fmVy1IOP4n3fw5/Me//HP4S3v85/GTe/zn8FN7/OXwp7/8cfirv/xy+jPd/Dm/l/Z/Di7z/c/hpvP9z+HLe/zl8Be//HH467/8cfgbv/xx+Ju//HL6S938OX8X7P4efxfdvx0cmMZ73kystgrihW85LuAhyh2m7epmamv5DIEld2Al/zeOq4RvCLXgpeTAFnwtvQBhDdnIPgcMIY6hOdhP4OoQxRCcfInATwhiak5sJvBJhDMnJTQRehjBOh8n1BF6IMIqfDBF4LsIYkpOrCDwLYQzFyaUEnoYwhuBkNYEvRhhDb7KMwOcjjCE3aSHwGIQx1CaLCHwawhhikwKBhyOMoTXZfwJhI8JFRH8Cf70C4NFEfwJ/hvBpRH8Cf4jw94j+BH4X4dOJ/gR+A+EziP4EfhnhM4n+BH4G4bOI/gR+CuFioj+BH0P4bKI/gf+M8BiiP4H/gPA5RH8C/xrhsUR/Av8c4XOJ/gS+C+HziP4Evh3hcUT/4wj/EGEL0Z/ANyA8nuhP4DDC5xP9CXwdwhcQ/QnchHAJ0Z/AKxG+kOhP4GUIX0T0J/BChCcQ/Qk8F+GJRH8Cz0J4EtGfwNMQvpjoT+CLEb6E6E/g8xGeTPQn8BiEpxD9CXwawqVEfwIPR3gq0f8b0v8IlxH9Cfz1coCtRH8Cf4bwNKI/gT9EuJzoT+B3Ea4g+hP4DYSnE/0J/DLCM4j+BH4G4ZlEfwI/hXAl0Z/AjyFcRfQHeOm2XMiwEu/B1224p7UVwcf6IQokrKBO43brYXvspWvF2Ltix6H+pQ323u7u+mpB7O1ZSorepedWC4m9wP6FeRxM4FtSwLpcnDIAhdgxUCjG3ltjvGb7FhJDIHB8cc02vJQ6aB5Htry2DHD0PQM5QC/GnhJ7PpwjGvaILw1EgfkxyvwyMIuxXZT/Xca//vLhjeBc0dHLgTNxEyh4za68ozDkDJ9vx/gjdly+bykQyOelRTh9+bZ+P7QWey+155rkjcBiHickI7TcUj3XLGz3lJrHdZJ4trzmypoVNctrGurFWz5KQJjahkNpK6alCQG0FmPbbdYj4ob98kSx6+6SfXixHy0TezuB/Sf21pow2EFJ0ip77ABXw9ZjWMNOccNhuRbZD5IrDcj+SeIHhN1G2MTezpKHlFAce6Ckm+BsJoybvfNKliK+z6Kigu/dyiRjiAGN9bAj9peS3QDXbTgi59pT802OmFyyipOn9BjT6BBqNEXs2liSwIuowWPDSdtvJ7zHsqn1piP2XyV74KsjHgUyX0mj7fZSrupXviaqcpgewNhjvdb9dRtS8rQa8yM7OwaWR3PsqV1oin6sKpZyxI4kWqBBe+8C0iCUpEFH7JgjDsLb47PFeHnCRmq3CSj2cDG1yGTuvH4ENREVk5kRTPcQkXFtSaPYsQ5y4M4eiKW7OkvQPQxxMFNnd/QCe2qJKXquPV4gdrUlHsW1iVj1onlD92giU2LNV6kU2hDoFhO6fDXdXEJ3NLEE6MSuJ0rux6a7/kKaTvx8HAIUmXi+DG23C/thohj/BaUEHaaiDtFJYjxHXfP3RtM++HIA+6CT0BP7dwVS2yxp03q+Iv1o7ca6LgZRRPODx8WeD3ISI8mVnF21JtJ3rA+LqXH2Yb+ZRHCWYjEuYFkEaprv2AnT58KuXGw0hViL9bAIpirC75XJ7xswE+geeJQOsKfBpHhDCCfDfnOPKbaxZAu4aZwWyQcELfVfhqD+zwzq3w1BfVcG9c+HoN6AS83e+cQx6mKzb89bdYVFqL1t3uzipB/JTF1XpGJFUMud/8dI++82KBN/ACsk71QT9OZzBDEk+Gu+iuAFnqAFCZ5QE7zFEyxAgmcB49mEnnIv7z5XnauKQWuPkp6Gfq55kiy7J269p5GEHxxEmFclJg1kG69vcZXMHKxkW2YlIazk0NFslbztwIGOjktkBG/taEvAmMJb8fb4TDG+OGF9Gf11+VEc67vQv8rsHSdS5s6HCcMlDsOXQOiIrS1ZhdRi71Mp4mRvJ17+koQHTsxNRxCzo27DIaqrufMAcf0FBnvVrscHYIzQaregkI5J/XZDr/UIjFdUog2VmEMq2GXvurbY3pEyRP2324Tbcvpkz2C8p5KgmIMmvVFM1ZrAYn1hzyZynZPpG5ASJhVGeYXYK6AcYm81s1Q1s9TOvuloztjHjtjXidXQI1twTIPc5g1tx1GqsSV2COQsxsHYol75nhi/GuTZsB+DXaN8AQkL52aEhXXfUJsd+AKm8Ylp4SQq3KNUMV/JUnm8+cpu8+i0XFAWMzktNAT0iDBKNuNiZz+Zz+3xGdgvjtgnYuyNxAtfkiBuj0OkrWpMmH94ew4yJcVJr6OjrjdiOx8jZQV0OGem175Quk6+HK0Lnd1JyO2x3BIMZPgdLZdphC2I7juLzfcqZpynVHa4HgWIP0AUqIuvM9Vduq5IHovzS35dbAKQ2zt6TXWxdabkV9AG5gf2+DoQeUCcNECzj52PEnuY5yVFw07zXd2oXE/ycvNPekw94pYU/YwTzbYETNpb6GDh8FU7zT/aQKLFZYfJtsFYdDloA6VxxE6Ik06IsU/FjncGREOPnO+IjQehHFUwHn5BYtcuEOPjHDG1SzZTOgPpkq/lMZi5jBLjgDaJvWTnSey60iR2iSReV4sdJ4wi+KZoj50w//A+uOwh/QdRENngmkHsNVK2ucDyArRlkovE+A0AtEOVc010mddtwiv2ql5sP/ZUdCt6nth3paMrZEpu1gRY+Wyd4NpXkI5tN1+ajmvBz1OpvskeDzfe7PHzcI66iDi2RePY0R+jUw/7DKd/sv9pB9Hqqo5Gn4Z+HHBcgup2fDCAc1F1XZdcUFSHlobeLsRRH9ueeOFT9Nd9dsgM6mJRsFZuAr7DpHbIEYfhQAfVeHvKUWKKjrHHwRX51lscsQ8ScawCGlgF2SxEkkaDeUMCRlvy4X/CFOY7peOYETBzrALFknWIOeV6mlJcPcVYDy5mt/0MonbiZyBxcjXImJDA3skfQAOD9q6DVLPEnqozRc8jo1g1fJohLsFIT/y0f+j85jpCdzQR7EfbsOA/RNaCEx725Jx+mrXcq+SoMI6JS8WLHfGQyVH1uQjdUilfNCgvst0PqzkxtZvkdx3bwT93gn8eiB7CkIPsid9dhHVgzE7txL6qFHMgSSHZCXbxREfVl+aNfwYhuBSptj8zRUqRFCn5ydAp0rySFgcIHLu6JIR5Wxtm1etJhIX+YJn3JrYtbX2ZJFBrDHgZ5qJPoYfJFHvTNDY+oXcJk/nBZ0TDV/be3GfJBJjqFeOOkjYw39o3xThtQEw9JVZ9tvYJe9eKE7AcMt9xlHTofnNnnQlrgoDpgHiwmGVq1sM268uPG4lkz6TtGQ/DeJklxvoh3s0Rx+8WDR+Lhl322GWfix1PmcTUdjTt6/bUU3VVn5m7thIWFASiKsppNz/4IQwjEtzqDD0Ow77oL5IvFNDJn+t0kmGbNwzPp11o+5h6ykOCflIuoiarv0DlIX/fcA1+i18qwnDOS2zopx50/DB4dC25wuzW8w5E7Wcck96wdpP13qRnzJ2zUZ5Ut6Oqf+0njtjnYNv9W03Mmfo+oeuQQU+oAtmsT2N8HSPGJu6qNpHpkU2Lxdy0iKNQjENEhpWVkfb3blbuYeU+I+3/g0ba/1wzLx8mDaPDHZYniD3/yEFx1h6mC5ddNhMxCDMMazaBbd1GmhXw6ybWzL2s3MzK+1mzD7FmrU+D2920krjcZ6p4C35D/W+64n93U27zgy+Jhq/F3tw9af+7m7QjVv197evogtiYmOoRqz5d+yh6cs9Xc8QLIHKi4xWj+XLFVHWR9XBd7Av7pOfEmKNkFU0n68z2bzhDPP2Rkm3KExZ2XXaczJPyR0MMurfIepItkmB1CUOq87gJfT/lgMZNmCQVmTvHGBB1yHzHj8nIQ78FesznJn0lmsVnMLqOFGO7xY6D0In98llibAD8uVuM524XY/mPkUa75kOA+coYXmZ92hFvgNgR+zuGFqjjE9Fsf1Gc9JKjy3EG0DWcYQDmPXi954NcsaO3v8784O6F8cnPgheJ8cmviLEWk2g4BsG9SOzoORE9tLBr7HG2WLb3fJNTV/XBuuvAAJARvCHGvkz0EBN8vKRr8py6qvfWLQGfBOUmipfg5GO2Q/x7Xux5L1c0fEmdHuwL6wOSmNXF3q+LfWOHkLz2IwzNJ+piH0A31BmOizkgO1S3di8aqRGNDmn5JWLHjUUkYhSTABktg+QM/bJw/Y0mASZKmATu6qND7vYPscaDfaOQLc2B/T1BTIlF0fFivBIH6ej1bcA6AqfdKwkrhMrehAO4cYV/xN67Ax3rJpej6wEykhjC41H7Z1x+C1zuwE3lLEQ5xkOq1C9eevVOITqOrEgaSlpwYwKHRV0skbj9PKiraofD7DjIotfj9lu+mTPXDA60E1uwmxd/lFZ+PASXoug5LLCMIOrmJe77kOr6qyQNU2TIkR0QpJ6goW5j1KEknc5uMyrT2S9ojNDlnM04ZzDOLYxzG95ehb5PHE+gAHln1lqgtuqEGL93T2QVjYwXQihdf2OlIOfdXlvbdzZWM46ImwOUZVvZ7kxqj3lrP6ku8Q7phd5EDBsF/VvITEfkKtHqn2T6Y/OQeLdQddi41u3nYDLdz80JutVB1qhXngPjr1u8ZQdumF1Vc3XNNTXX1kjXbFevzX82xNq8M2Mlv1Gfuu8GNekPhyANqXKttXpk13G51mVfcbnWA6Bn8mLAcASjP+YI4kiQOqwiWMgTXIcElR+rCH53mCOwI8FPDtPO840Hacbg0llJdh47l07JxclaEv0hhYXLyS7cAcS9JFxj3URT2jXalFa+RqX+TD31L9x2rL5a2HrhimrhMVxOPhqBb4nN75Plc98tg7n9qLTUP/4Aw8QHiauAiCTXaYGHnUvSTnMnbuZg6kmkN2/4CfHYZ7VpqDznlFcYg1KM+oBmsK+9h+Z7va8C5CWzDhmvH+BAQMttZAviRv7yFcplFL8RE+UWkig3MSEdscP/Njnd76N8nySmUDn5JDpEkujrMNqrU6p/qcEv3qMj/IlDmhQc1rdQGQxxOxniVXSIt9Mh/mxiIxMw9mLilkPcEJfPolucV39A/XTHeVhXb+KJ88iGJjEqusM3yN8Bc7AA/X9CWUqlREjwNqXBuHod0rnCqB39k436seIsI922adxWRMbHe3RPHZQcENimAixg4qEELGxPRwUQndj+D6oNAlvfh3XTY3jPLeHg0CJuMCeeeV+1kzHikLKTYd7wpIGuYZAY1vHJNw1E+eTeE3S3a3BD19z51Aklsd1ygkZtlcofZ2yi7jDoq/wgXKND1NgAkuPDyo864Fvi+Luw7Lsf/iRf+orJQAO/uXP3MSJAkXkDueugngB++w/qHr98l5sAkj85xuqgKqolfjhHswC+Ts8hVaOsD1pKTjDRyLVq8MoniZfwypMFvP+kEk8AMk3xIFLgk9xc6Jycw22cFiLBGJ6AGwKfom6YDib+9g6QjcY9M6aZsguVdpjsu1Cq0aieSRbqKV+ZTRTPu9Tcpe+ot/GTv/iGmxc4humkX2wwm1aTmwco3Fbi7v/9D9xgGlsCfRydgvqYiFNC7tD1RC5+j/8ldyIUHS8YEimope8C9NACA10NPf8OdXfCFDsgxp5KXPwunYswB8dLuKBIfPmuahDkv0P2ZiH/Nm84hw0CpLNZU8mZdBBAFtNfZSGrFirRqK+qWFIT20gEQ8WxkSLMfaCCRoPw75sIcpllsYEQ6bonSkTU5PF3qcb4Q5nETe/QMHwPlA8bcEx37iOTFMye5g3Pk/0p9Qxq7nwwIzXZMES+EVFMY48VoDz4lXqY+n5Whn+ZOwcyGnphiIwJqbIZ4tjbdF7efiCV6twvk9T+bwdxjqa364jSDxvTSuNiMCNt+Fd64gYmwNwDtEf2KL4+25hdYvvbJAf+80yV9zw+83/Qe3Yd0PGedQc576l+W7Xb/ulb3I7SIrLRnqPcKtmG2w8J80GyyKWbtouKMLce6YhV4o5lrj21AJEmXPWy1a8lveVkM+FQ63yL+OYS6KVXiGuqb0+Suy6nkDSTQcr2V377ZjrMvp0QD+D2H7T3DkQj2t7f8Zu2vb9mTNPxIabpVp3uXvkW+kcqcf6bNMSVQYjbumclTGubltEb4S3YG9ps7Tdv0aXabpY2XUfSpuZ/Z87U/SaN0rftp96wWxhc53X//2vWzpodzZrt5ppl+2SYr0Gz49P9536L8rz1BuVRngJgN7SvwzyrEdOuqES/xv99g+Vn++m82piQ3lCSPVlMJ3rRy7MlefICVYvj9Vo0Y5J59M3ss+K4/cqM/t7rdEf6+TdJxmLdn5z6dXaevjeouz0MHEnha7YBkf15DxNJRr4UY5eV1KxfZ4IU9vVcHHfrirY+Cxmj9eVHcf2e2ELUHoABMzNPdXP27dcHdxaz3xjEnUUMtjETTJ19wzyb7Lf0ksdKlFtKN9u7cgvEy1M5WCc0XmN2HCUrpniR2LW2pCjx+OvkHh9d9XJtu15XdtnYfWGydyKXFOHd0EQ+iD36jcxburjXhvLAUj/2ceJFtC+sgy4WcR0EWO0Ng+dI2vBJwrMP7MjuF6JslYn/gspBqg1VZPMyt8QRLyNZeAveN3ucNGVe/FZH24DQNgI7bt5+DDD5mMebxC7Huanbx5o4bX6yT3lQpuYJos4l5q2vkMdScAOsa2NJP2r04j4SQlS7y/bYR3WxT7iqFu7TGGbrTwfvdQ9gNQP7shrGHr8MTHBlAh9wqesKJOyXrkhEzfiAyo9eJ8revb3PaN2PBismBjuN3ePdGW1EI9X8HcPqIbmAzLTyGZ3762LH+6Z4NPfD1FMvkETn4vSZ83ecv3Fb3WTu3HscnPcAvSE2kH6wqYU4TX+NuScf5s1ccN44LfquVA02Dz/YCBkt+hpUZKv0yBbXxPO7xFRNrBCUvnN8iiy5cYDhU6OJ20HQ5MiUan/jUna7ihB4kWCSmuBvxzkCEQl+ixg0xi07cBhyu0g4b+F2wh5yS6QOZqddJDpqnLNzTsb0dIZmeuKUSgrkZvSuvnXckqTven7GsbL+u4purjRkpoafZSzidhv0W3zYMLjUwfpf2ss0jhdjiPeSEO86hZmF7yNtpCaG/eQ1Okv87VXWUi975uFo4m5Qjq6fb9hLx0dvjrLYwLM06GJj9t9p+kMwf8JFMz4Ymjj6Gu29ibl0yVAMZeKpvaolwyuvDi4ZrjLSJQPS4ZJhDT5XRxo4/pq28dvylMZ79tLGCeYFbPwsIi9rfFMebXw9lAmbuvEVXOMLWONIh427MvMSYqynXqVrg9tfAW9sPpExmxCiX75Kk1s3Es0BIrIFl2xKr4E+mkyzWLQYZLFfTh7MYgkK5mq0mpLFhnK1y+z/m5HU/UjQ9am+KG21lbWKpoJWb+ZaJSi8Q5k32Oq+PE3ufLPKyb6v19qCbCZBeylqKbnzKnSImtdo/7UhkAuG65udjX8h40cBFf7d2KcGxo8/z0rseIW68pusPPQKTQCee5Wu6tG12JILv57kkuvb13a8+hHFjVhD+PUkG3ouI1L8eohI0WXI7qLjXiYrpdsuVvnYf1x8aj72L4WUX7yk09v1r3C9febLqpVS7x7uVmgdWSnZ0hM2XSodepk90EnWSnXZ1kp1JrxRyuZ6S/qGaS1dKzUblbXSSmOWtdLlGZPD94aYHE5AK8lbdHrhZ3tILxgnqcbciEmnOOb+lV44c4/OmHn+JW7MbNqj6oWaF7+1F6596V/shZEGpReMhiy98F7GeHtcf7wl7xNYVF0n0FXPJ89zm4N3vchWre8dU1at+49lWbX+IaPN9UOM8UA2c//uBbqGCD6PZs9ZhStWC6xY+yZno25n1DWUWru+hfXli9knl2rGaALGpPkYeT69ZkW92PFRsT12wh6/1oJ5wiUkT7gw46GbP7AHHp55Dh+fmm+h2eW1xUPx/JTx3EN5ihlP0VA8nYynifIUcU91nU9YxqZXqdteoMF65nPpJ7rEjh3FV9Vcq7o1KC8f7A1HSW4c/vXZVQRX8AQjgWBkn01FsJgnOB0ITu+by6Wbh3ALvquiJPEWSEK267mLx8hFucSU2IZXP1JfHZ2iV4sS/wevGukt7Czrx6V1sR322Av22Gti7JhY9bk9dtRhrjsmmpcccMSOiz3H59jj8032+AqLPb64SByfdBi+AqOJsQPtBfZ4a7FoOCCaH/xMNLwgdlzWL7SdDRfbc+050IPmB98QDa9DBrc7+WMyrGxQz/Iie7zOAss2cfxeh+EEqeptrGodVPU28HwlAjZe0W/DEX+kLWQHswBfQ4mF0QKwtoQRfy0ajpLfQkDjXwnmDZcYyMaDGNuHZHhj2LAPyJ7Ce/O9uT10Jfa2I/ahI/ZpXexg4gtyC6RbLdoBsefEHBAPVMNHN2Jfo3jLix2Gr+njJ3tRPCqdd1A6Qppi0jkMqSzSdZEsNreEkA4wCR2GAY2E5PcEioTLTuAmaG6JvarbYXZ021PdJ9kfn0JLu4HGYr8gUOQwHOf75XXRgAvoBP4yjluyZPUPGMN18dkkZN1PN/aKzRt+RUbPOHs8aBKr+uTWmidwoPVVqrz7e5njg5sWJhDPznkGEqyxmxzxS/BO5vnkTuZY5V6ro+qD6B/xPukfd5OYREfidmjyrejz0DwOXhOO1K7dNARt2M2PWJVq2v2TFbhzsp4kwCfIkr8YAxr+4i/9C5K/PQ2tVv2CIOWRsMJDcogC12wXu64uMZF0H+leBB22zsVMfxLDdD1NtgnoEgkjC3n6B292rM01xeXciXiboxhVL0byj1G9LtxSoPc2FgP7rs4SfBxvAsWDaAiRZ38SU59WFkHRp+mdL7phcllJ4gtAVP/VgKbFNPPC3fh83Vb8tfxjeNQQ4nqepmuXeN5Ri4X8egJEG5UzXskDHLkmvLVWRDMA3IQ7yel/rYHMR1hkTP9tuBF91m56166Izv1rS8TEq09TzVclfr6bBt0/U/H6riEynvwG/7e2/rNeME0nLMiNKZqDN0KLyS9PkPmqHoOfspq70ZT4hj6pflXygt1Zr7/JnmTP3c3oRuzCAJv2Ly39A4z+1V5Gv3/nkPRrGf1/KfT/vZN/PHbT0sQsaDmR14vSzRMEGK6xVM0Ke+xIzXII5TUNjq4LQ2MswnKxa0oblPWOSe9Z90M0z8FfyCZe20F3zM4b/D0BxJsj86CO1OlvwhAzwKiOfkjG0DXKINrOyfv5dvZbW/bTWoPqFIMs5xQ2u1unRuRmb0Boino87rAwNRoJTyUnAOGZjlND7XJLMFBeWjG12RuRp4Scruudq90Rgg87A+y61zUVD0eJTA00O8NhZ3tpSygktAa9zZaJzkAw0O4PRiOWgNPvjkAF7kmzZilss2YRvlmzGONlvmBg9eST5gpFWpwhN2GabZk9axaeAOV1+rw3uCVPOOiX3G2h8ERXMBCRLTbLRZMsVzVYLrfQJkL18PWfaWcyVHXynIGoP9QurUZBLqOC/I9ZZLKF2cVy0cnzg4yyd3UU6KRAMOwntmyWIj6vy83qu+ZfdRFiES9ahLjJqVmS8F32v2DD2SoJmFPxMtWEV4dmEyeDb6fiIf82GSdbUAZo+n/P0a4RvIFWcJpmi88ru8NOn8UTDJPLEydZ1njlFgseeWSxls2aIPAHUM2ahedBodjhqAvt6vNZAkHZQuoSLMM1xJFoE3wV7FOXWIIhaAZPS7LA/+Q8omaLx+tzC+FLhPlQWsYjSYDIgefSAb9QG4z6mgMTZHYFqVg8XGydJi1wLJlb45CkxZK1UlF7OtHaWrbC6Yu6bXgymO1k6MvrZSeat1lhGZq+yqYc/WQ7OXnK54I1eaYidg7Opu9Xq87XSZ8Hwq6vYte7v1+d9XoZwx/UuS4o+JXq60PLO9O+hLPdSeg3wxZo9YaDAb87IGs41fKEVmaXR7lezfAPaa6nz8Vg+uCamtCxUns+ZPpcjJVq+oPfQm/R0BfVq+kN5+RcupGdnWN6MpXCx0i2dEMJ0/frUGKGv7snlcKdkn1QLoVy9z9SqdugbOlPpbqhNH2WSh2EcuIXQAd8pi+BDsrio6kU/n6xEkr8BUALlPiYxr1Q4g8R9kHZj/tZA6lUJTvcSDljx3DDMsHQVmQ4Z2SBaZOhoOh0dn7NJJCJP3clOz09KwbpJz6RSj2EdRcWzS8sXmgesca0Xpgz5tKLy0vO5/lzNPxKe/dDe/x51mPT9EsdhKMgB4+8zFH4Ktg5NeuB793xgpD73LXVQk1h0dzC4rmFlrmFE+cWltUUVi4o3JzfUbAxvyvvjtw7c241Er6r8ayTd1OpX44EvlWrsvN1F6r4UJ4deH7Lx6nU3bgYmFtYVFNYPK+wrCPnDiOV5xD2N/TVmZiSZdZZU1itqpKeG4y6sr59STh5PtS9BPgeAr5RgMutdCp61BRaQO2cjtw7gBrti6n5veAz57L6O4zU7qjHZsBfqME/APgtWfD4xOGeLHh8rHEf+PR4hlfOOa+A6weB3i1Qe91ptBUW35FjK7R05doKJ27MEwvLbs0XCys7CuoKq32oKeg7kegOFgBdTKT+tczXtZluKufODiHn1hw8jAMPPLHhqSXXMWAlAvhzCjy65DY8byRqoEdOyXilxkjJrLiHtYIBVQisz6VAEf75MwO68c9RBryBf2ry6IFaJWfBoAiy02YnI7Atj5JV4O2nVwEoVw4gKyigh22tBa0MkwqoOJ2o4hwTPUbsjwj8cTg982szAk8Mp1ceRGD9CHp62K0I3AbAAWXMeKB5PAL/SVShF4Bhyqlke86iJwEZUO2Hi2lthOzHY6jUr6CJnhtDD7SagUe7jIA/lynHoC04j4qzHw9xaR1HeR4ez8y60qg6sT+V88otQs4eAryhdNQbrE+CeEzPMAPV4TdYv8yA4wj83kDP5jIi2ecGymNGAM+xMCnyFDFjV6Pu5+fR854WIrA4jzuUSznhfC5e+U9G1o3AswD8Tanth8OodmPwj2kEszye73Ma/Ikb0r62R8hZTE7eVxrALyG8hEAPf87ZK+wwt18h99vsxK7fGBhtoUH47vPd57vPd5/vPt99vvt89/nu893nu893n3/+U3Qu3WcqY+9x6x+r3qcy6JR789TwQQ18nMHKmdKNxbRe5SzpHWyfSzk7WXmPmHJmsnJW9BhWJth1ZX9HOQv7yxOpIJb3Gml9yup13zAKp/eGciisnIm9l11QzsJWznY+Q2Of9Jne7NxlZdUaylPvbylnditnRydOq1bhD46uVsltYoYapmn/RIrqU83oUwxW5Ohn8J+Kqv9H/ST9HjvN5x7Wr/ex8hFW7mLlXla+z8ojrMxn77k5k5UXsXIGK+ezcgUrPaxsZeWtrLyHlfex8hFW7mLlXla+z8ojrMxn+6tnsvIiVs5g5XxWrmClh5WtrLyVlfew8j5WPsLKXazcy8r3WXmElfnsPTxnsvIiVs5g5XxWrmClh5WtrLyVlfew8j5WPsLKXazcy8r3WXmElflsnJ/JyovGZvenBbW1sywTlzdFA3LUUlFaWVoxZVqUQNabrBWlZRWlFZMoXmBELp8zsNrS6g5H8N5Leen00rIpFZRl2k1yOBqR26dZJsrO1ZGpy2wOW029TSqfXjbVg6/JmGSZiLeBmvGWjcOxoo6yTxKE0ki7X3Y2QSmHadmifPMGZHc4JJQGgrK7tGaufQpUzaDVgWhpU9Tra57ibRYI1OKMtAilze0BqI+WcpheYQKrAAmuhd0+JxKybyGfjE164a/sboO/ILcXrgWbnbJTKHW3SJ6w0++WWprDgxBU6nKxV5RIMnkdEqlDIvfXaB3K9+tcYSKY0+91AV9QJn9ou7SNpkhEKHUF/Xjv418e1+ewmK3EtcH3a6r307XzgfK5QFC/E2Hw/ZUUtmjoczWwVcMvM36Z268eih/3i49ATFT4lXngXoZoZvg8zbyhfBazOcComSeUgLuPzRP5THeTJl6vYKRGzbyzb5h6ntGz37Usxiv8Slz/E5sA79LIr3mNqHA9mzMUWJk3qtlLFTYLg/LnZNH/BmZTo2aeOjhaPU9p7afo36nhV+a9xGnqeTKP5QJa/juEwXeu8nlCY7F6/tfr/5iGfz3jX8/4H8rR5Dua8m4Nv5IHlTHHv2tmdn7l83MNv5LX7KhXz+968m/WjL89jH8P47+/YOj279fwD74HlsIbv6X9RzT8pqtZnnI100dz80TrP90afrydRkt23Th0+y8L9NZGjiYPVN4zq9VX2z7+WM3M8St5YsKfnV4Lf8jkT+dXjL//JPk/4cYWnycp7wFWDJOv4Vf0GtC0r7yHZyA4dPtKeVzDr+Sp5A4D2sEwNH++Qc2fYO9pSPzg5Ow/kt2ISbfP3uczwPhNmvGnnQ9Gs/bLtPkm479VZ/5RytGC+r07yuemMIsfhqHjL++7/KfxRlquYi+zwXtYjizxa5hO+1tup+XXo4duf6hPDlAr87Eab0zPs2p8Tnr+VONz0/OiGp83ON+p8PnpeUyNL8i67sgBqyjzjho/LD2fqPHD0/OEGj8iHf/V+JHpuK7Gj0rHazW+MB2H1XhzOr6q8UXpuKnGj07HQzX+tHScU+O/l45favzp6bikxp+Rjjdq/JlZ11s5sLpU4oMaXzw47lX4s9PjWY0ffO+pGn9OBs5AYvanKS2evlMm0w7zGR4fj1CNJ4bHxw34z3Vk/A32o/IuottJ22OEPM37Ux9l9MpzMhdycRzxyvM5Cv48A8Urz9co71JaxvAHF1H83ayBtQpeU8/vGX7zEop/SYm/DF89h+J/yTY8fm2k+PVL2b4HCzLPK/g6tv5i+NYcqm+uRt8NBG9OPyekxJ2/MrzyfJKCTzC8oKE/J5fiH9Lgr2D4PRr8OoY/qKn/vxleec5LeWfSfoZXni9T3oFUmEfxZRp8DcMrz2cp7zRaw/DKc1kTGf43DK88n6Y8Y/QSwy+9Sk1vyKf4fk09FQxv0dCvys/u59cT+sxx2pbP+lETf7oY/iENfjPDa/fXHsmn/W7Q9PtOgs+MGx+xepR9u/R8Segz44+eXmcVIP1oYbdm/F5YkF1fQScOWAl9ZvxZQPLW72XI38jwWjmvJ/Vkxj25AHOGzDh2c0H290P/Sgf/DMHDOD1XvS/4JcN3s3ii5AJ5Joq/QtNfI03Z3xu9yJS93ZAO/l5T9veR/04H/7hOPS/q4D/SwRcMy46vJPjMeXO2Dr1LB79GB3+7Dv73OvjXdPBHdPBFw3Xej66Dbwb8+UbwB6avsg984/Ds7+feqlPPS8Ozv7f7yPDs/YgPB43m8hBlPTR+RPb6q3Xwy3TwN+vgfzwiuzx/HIE5fub4ekynnvdHZH8/+oiR2ekrRmZ/f/nKkdnf474O6Y1nCwMaeWI69f9+ZPb3oHfr0L/F6u/X1P+hDv2JkTQOLGX95VbmtVHZ6a/Xwa8flf399L/Soe8ehTRjMuzwnA79B6Oyv+d+bGF2+st08E4d/A918L8pzO5XWxh9v8ZPDujU85kOPt+cHb9EB+/UwbebqT1NUbU9b9Kh366D/7uZ2ll536wS/0cXZaefWcT8U1bHE48OfWcRHY/afo8z+k3nqO35gE49xtHZ8Wfo4K06eLsOfvVoqpegyVtu0aH/uQ7+SR38Hh38J6PZeGTz+LtswfAFwWdZP04NB4Py1FC7U3YFm93hqaFwsMnn9kemOptc1vKqqbap+CZqif0mqdQVCpEXUvOb9dYMzLQMzEwh/XOFSLRJsksZtUor9X7TYLVKEt6mkIFDclQsDgbou+JP+icn88roy8BP5Tch/xTPtJPgqcCfzZwUpfKrj28TJSp7faBvpMUZdjdLYbfHXi/PaHW75GDYvri+TKK1lUfkML7CvX66ZLPZFAEWnYzNicgzPdEAVlmJPwbyeQNul8++cNlg/YTIhlU3uHyR8BA12dJVREJICpI122Z6guE1znCzvUGyeUJExNCS+ippKCEHFXO1+pg+06ZJilupfKy82RMBiZf56qdJy77F7uyHXXbfYjDWDPqDLftCnw+1s9XXSPC/zYaaVyA9SNxQJjVYpYZpUkO5ZLNaw+5I1CeT197bltTXSkvq58E/G/ybD/8WoE71sqNSkrxBcqtMWtlgP5UfUJ0EvfYHTifDovnN1UmwZPmZ0bdzDf6Y6dtpq9Qq1J+ilepP3Ur1p26l+n/KSvWnYKX6U7LSilO00opTt9KKkxXeFZYjctTjKXUJkrSwdpnksNc3SJIAU417tTciu8OS7JdcPojpESELSpKag9JqX7DJ6ZOaIfpEJGe0TXAF/SGfW3Y3l86oqpyWnUgavGssgeHD7QK989wc9fvbgYWDpMGbzYxUkuYvq6mzSbbF80BYKjn7zrReMn9+vQ1Gfs1chw0pVFU0qxER2RmGUT7v+4tr6uy1At6mVnArF9dHZjhDIeCxLV3k8ldXL3DY59Y2NkrlpRUkoNWDA4EqzZLPGZGlQFCWgh5CmoVWL/hV1dU0SitqfMttLhInJZ+3ySW5IlFiJCEtTMOKetk6nf/JaFPUY3cB0uqC2UWSw06vHLG7cB5x2WxaAYBuhiRBi8E1UpOzWXKBxK0ZUtYHq6Q6ME/EHZbtEFOX1QcbJBVVaRWIuNofDFDB0OoLW6VlzDtqwRARdI2Vzb6lWaqPzIT46w63um1aC0nICPV5nF4fuyRNK51WOp0aWp7uIvHcZbOWg4RrvM3uAOlGm7qVUqtVYIaD5uRKbzAi4WMZFXagrbVqqAW/0+cLutTtefAHtBoRaKdQjbHzMiSsj1SAEUJV+ItfmEFlUNC/bBHpCq0VAmvwilwF7kJ6Q9ZawtXmlKCGNq+c2YxsLQ9HA7IXhocbRzGoBJVFMnt7WpnS28EouqUErrbaDb6Z0Ro+8wLu4PNJ0IF+bwCaRndrgLaqqLsFqb/BX7fTf7Iu51ntliNZFFB3ybyMLpHsDXXSYAhqqKvFaNNAnjyR7EskcrCDFI24m6ndwQJ+V1ZTe8JudxZXilhnkjHr8YaHHLSgri/DEVC47KJJ2tBBHMJaJqE2UFew3abjEOjeVW4lhlesaXHKttaswaacE1w30igtW8EXWY/6MtpssGe4ktYxQD0lrjI7Q3s6KtTLFS7ws0x0VdqntBpJzZGg1ALzNRgPn4cK+rKOOQyELBGjISxI3VAJUlm8EaIW6Dbouui0JA+01c+Qli6qL5d82pDmd/v9wdYMb0ErDfaMVjsMcUOP5KZIhPOI4HSPLxppyexbnLLLcNy3OZu8rVYcuhEvDkxgx6gHunqCYHPgqJlrl6yl5ZqhhCuGrFEEoxvYXuJ00FYyqJ9eLTiO9GqQQqA6rBik693tLPJljVOZ4xxM7vKH1BZ3ZQnHVEjam6Bv1g6f7vK5nbCCkiHzsYNN4J8MkmjCgTvo0boYqkf6Tq0VyRLIuDyFGZcs4jRKesjhDRlupZ7KwT91Ks42i8/kZ3Fir1a9EACOVC+5/SG5HWJWCJoKhp2r3bZsfdwEMS0As4DsatGYgjy4B1N+W5sUcocjQYgmXqiwtSzTlU5xvoCIgn5CemwJzLn+YLM7y2SZRTs262UEv+WBNRggl8Eaz49V1dYCvowKN4Mc7uLOMuGAVWeyIZwlISoPRWWbK4sQ4Gt1Evjd9RDFYMmRxb1D7YM9b61QJ5SZszbmFQKNdf8PqfKXpLKcAAA='
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np
MAX_VAlUE = 1000000


def dfs(x, y, edges, deps, mark):
    if x > y:
        x, y = y, x
    if deps[x, y] > -1:
        return deps[x, y]

    e1 = edges[x, y]
    if e1 > -1:
        if mark[x, e1] == 0:
            mark[x, e1] = 1
            d1 = dfs(x, e1, edges, deps, mark)
        else:
            return MAX_VAlUE  # ループ
    else:
        d1 = 0

    e2 = edges[y, x]
    if e2 > -1:
        if mark[y, e2] == 0:
            mark[y, e2] = 1
            d2 = dfs(y, e2, edges, deps, mark)
        else:
            return MAX_VAlUE  # ループ
    else:
        d2 = 0

    deps[x, y] = 1 + max(d1, d2)
    return deps[x, y]

def solve(A, edges):
    N = A.shape[0]
    mark = np.zeros((N, N), dtype=np.int64)
    deps = np.empty((N, N), dtype=np.int64)
    full(deps, -1)
    ans = -1
    a = A[:, 0].flatten()
    for i in range(N):
        if a[i] > i and a[a[i]] == i:
            ans = max(ans, dfs(i, a[i], edges, deps, mark))
    if ans >= MAX_VAlUE:
        return -1
    return ans


def set_edges(A, edges):
    for i in range(A.shape[0]):
        a = A[i]
        e = edges[i]
        for j in range(A.shape[1] - 1):
            e[a[j]] = a[j+1]

def full(a, x):
    for i in range(a.shape[0]):
        for j in range(a.shape[1]):
            a[i, j] = x

def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    A = np.empty((N, N - 1), dtype=np.int64)
    for i in range(N):
        j = 0
        for c in stdin.readline().split():
            A[i, j] = int(c) - 1
            j += 1
    edges = np.empty((N, N), dtype=np.int64)
    full(edges, -1)
    set_edges(A, edges)
    ans = solve(A, edges)
    print(ans)

'''

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

graph = [[] for _ in range(N * N)]
ins = [0] * (N * N)

for i, nodes in enumerate(A):
    for j1, j2 in zip(nodes[:-1], nodes[1:]):
        n1 = max(i, j1 - 1) * N + min(i, j1 - 1)
        n2 = max(i, j2 - 1) * N + min(i, j2 - 1)
        graph[n1].append(n2)
        ins[n2] += 1

visited = [False] * (N * N)
for i in range(N):
    visited[N * i + i] = True

que = deque()
for i, v in enumerate(ins):
    if v == 0:
        que.append((i, 1))

dist = [0] * (N * N)
while que:
    cur, d = que.popleft()
    
    visited[cur] = True
    dist[cur] = d
    for v in graph[cur]:
        if visited[v]:
            continue
            
        ins[v] -= 1
        if ins[v] == 0:
            que.append((v, d + 1))

print(max(dist) if all(visited) else -1)