問題はこちら。

愚直にシミュレーション。PyPyでもだめだったのでC++で通した。想定解法はグラフの最長パスを使うらしいが賢すぎて思いつかない。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)

const auto id = [](bool x) {return x;};
int N;
int A[1010][1010];
int p[1010];
bool fin[1010];

int main() {
 cin >> N;
 rep(i, N)rep(j, N - 1) {
   cin >> A[i][j];
   A[i][j]--;
 }
 rep(i, N) {
   p[i] = 0;
   fin[i] = false;
 }
 int ans = 0;
 while (true) {
   bool update[N];
   rep(i, N) update[i] = false;
   rep(i, N) {
     if (p[i] == N - 1) {
       fin[i] = true;
       continue;
     }
     int j = A[i][p[i]];
     if (p[j] == N - 1) break;
     if (update[i] || update[j]) continue;
     if (i != A[j][p[j]]) continue;
     p[i] += 1; update[i] = true;
     p[j] += 1; update[j] = true;
   }
   if (all_of(fin, fin + N, id)) break;
   if (!any_of(update, update + N, id)) break;
   ans += 1;
 }
 if (all_of(fin, fin + N, id)) cout << ans << endl;
 else cout << -1 << endl;
}