stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
// 27/07/19 // 16:32 PM //

// O(n)



#include <iostream>

#include <cstring>



using namespace std;



#define MAXN 100010



int n;

int value[MAXN][10];

int memo[MAXN][10];



int funcao(int i, int ant){  // ant = 0, 1, 2

    if(memo[i][ant]>=0) return memo[i][ant];



    if(i>n) return 0;



    for(int k=0; k<3; k++)

        if(k!=ant)

            memo[i][ant] = max(memo[i][ant], value[i][k] + funcao(i+1, k));



    return memo[i][ant];

}



int main(){



    ios_base::sync_with_stdio(false);

    cin.tie(NULL);



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



    cin >> n;



    for(int i=1; i<=n; i++)

        cin >> value[i][0] >> value[i][1] >> value[i][2];



    cout << funcao(1, 4) << "\n";



    return 0;

}


// Optimized solution to the same problem (faster):
// 27/07/19 // 16:32 PM //

// O(n)



#include <iostream>



using namespace std;



#define MAXN 100010



int n;

int value[MAXN][10];

int memo[MAXN][10];



int funcao(){  // ant = 0, 1, 2





    for(int i=1; i<=n; i++)

        for(int k=0; k<3; k++)

            for(int j=0; j<3; j++)

                if(j!=k)

                   memo[i][k] = max(memo[i][k], memo[i-1][j] + value[i][k]);





    return max(memo[n][0], max(memo[n][1], memo[n][2]));

}



int main(){



    ios_base::sync_with_stdio(false);

    cin.tie(NULL);



    cin >> n;



    for(int i=1; i<=n; i++)

        cin >> value[i][0] >> value[i][1] >> value[i][2];





    cout << funcao() << "\n";



    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ld  double

#define mod 998244353

//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n,k;

int arr[100000+9][4];

ll dp[100000][5];

ll solve(int ind , int last) {

    if(ind == n){

        return 0;

    }

    if(dp[ind][last] != -1)

        return dp[ind][last];

    ll a = 0;

    for(int i = 0;i<3;i++){

        if(i != last)

            a = max(a , solve(ind+1,i)+arr[ind][i]);

    }

    return dp[ind][last] = a;

}

int main() {

    cin>>n;

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

    for(int i = 0;i<n;i++){

        for(int j = 0;j<3;j++){

            cin>>arr[i][j];

        }

    }

    cout<<solve(0,3);

    return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ld  double

#define mod 998244353

//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n;

int arr[100000+9][4];

ll dp[100000+5][5];

int main() {

    cin>>n;

    for(int i = 1;i<=n;i++){

        for(int j = 0;j<3;j++){

            cin>>arr[i][j];

        }

    }

    for(int i = 1 ; i<=n;i++){

        for(int j = 0;j<3;j++){

            for(int k = 0;k<3;k++){

                if(k != j){

                    dp[i][j] = max(dp[i-1][k]+arr[i][j],dp[i][j]);

                }

            }

        }

    }

    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;





int dp[4][100001];

vector<int > a(100000+1),b(100000+1),c(100000+1);

int max_points(int x,int i)

{

    

    

    if(i==0)

    return 0;

    if(dp[x][i]!=-1)

    return dp[x][i];

    

    if(x==1)

    {

        return dp[x][i]=max(max_points(2,i-1),max_points(3,i-1))+a[i];

        

    }

    else if(x==2)

    {

        return dp[x][i]=max(max_points(1,i-1),max_points(3,i-1))+b[i];

    }

    else if(x==3)

    return dp[x][i]=max(max_points(1,i-1),max_points(2,i-1))+c[i];

  

    

}



int main()

{   int n;

    cin>>n;

    

    int i;

    for(i=0;i<=3;i++)

    for(int j=0;j<=n;j++)

    dp[i][j]=-1;

    

    for(i=1;i<=n;i++)

    {

        cin>>a[i]>>b[i]>>c[i];

        

        

    }

    

    cout<<max(max(max_points(1,n),max_points(2,n)),max_points(3,n))<<endl;

    

  

  

    

    return 0;

    

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

#define IOS ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL);

#define int long long

#define pi pair<int,int>

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007





int32_t main(){

    IOS;



int n;

cin>>n;

int a[3];

int dp[n][3];

cin>>dp[0][0]>>dp[0][1]>>dp[0][2];

for(int i=1;i<n;i++)

{

    cin>>a[0]>>a[1]>>a[2];

    for(int j=0;j<3;j++)

    {

        dp[i][j] = a[j] + max(dp[i-1][(j+1)%3] , dp[i-1][(j+2)%3]);

    }

}

cout<<max(dp[n-1][0] ,   max(dp[n-1][1] , dp[n-1][2]))<<endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define N 100005

#define MOD 1000000007

#define dd double

#define rep(i, n) for(int i = 0; i < n; i++)

#define REP(i,a,b) for(int i=a;i<b;i++)

#define rep1(i,b) for(int i=1;i<=b;i++)

#define pb push_back

#define mp make_pair

#define clr(x) x.clear()

#define sz(x) ((int)(x).size())

#define F first

#define S second

int max1(int l1,int l2,int l3)

{

	if(l1>l2)

	{

		if(l1>l3)

			return l1;

		 else

		 	return l3;

	}

	else

	{

		if(l2>l3)

			return l2;

		else

			return l3;

	}

 }

int dp[3][100005];

int val[100005][3];

int fun(int choice,int l,int n)

{

	if(l>=n)

		return 0;

	if(dp[choice][l]!=-1)

		return dp[choice][l];

	if(choice==0)

		return dp[choice][l]=max(fun(1,l+1,n),fun(2,l+1,n))+val[l][choice];

	if(choice==1)

		return dp[choice][l]=max(fun(0,l+1,n),fun(2,l+1,n))+val[l][choice];

	if(choice==2)

		return dp[choice][l]=max(fun(1,l+1,n),fun(0,l+1,n))+val[l][choice];

}



int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n;

cin>>n;

for(int i=0;i<n;i++)

{

	for(int j=0;j<3;j++)

cin>>val[i][j];

}

for(int i=0;i<3;i++)

{

   for(int j=0;j<100005;j++)

      dp[i][j]=-1;

}

int l1=fun(0,0,n);

int l2=fun(1,0,n);

int l3=fun(2,0,n);

int ans=max1(l1,l2,l3);

cout<<ans<<endl;

return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#define max(a,b)(a>b?a:b)

int max3(int a,int b,int c)

{  

return (a>b)?((a>c)?a:c):((b>c)?b:c);

}

int main()

{

 int n;

scanf("%d",&n);

int val[n+1][3];

for(int i=0;i<n;i++)

for(int j=0;j<3;j++)

scanf("%d",&val[i][j]);

int dp[n][3];

for(int j=0;j<3;j++)

dp[n-1][j]=val[n-1][j];

for(int i=n-2;i>=0;i--)

{

dp[i][0]=max(dp[i+1][1],dp[i+1][2])+val[i][0];

dp[i][1]=max(dp[i+1][0],dp[i+1][2])+val[i][1];

dp[i][2]=max(dp[i+1][0],dp[i+1][1])+val[i][2];

}

int ans=max3(dp[0][0],dp[0][1],dp[0][2]);

printf("%d",ans);

return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define REP(i, a, b) for(int i = (a); i <= (b); i++)

#define PER(i, a, b) for(int i = (a); i >= (b); i--)

#define rep(i, a, b) for(int i = (a); i < (b); i++)

#define debug(x) cerr << #x << " = " << x << endl;

#define SET(c, v) memset(c, v, sizeof c)

#define pi 3.14159265358979323846264338

#define all(S) (S).begin(), (S).end()

#define INF 0x3f3f3f3f

#define mod 1000000007

#define pf push_front

#define Pb push_back

#define mk make_pair

#define MAX 100000

#define S second

#define F first

typedef long long ll;

typedef long double lf;

typedef pair<int, int> ii;

typedef pair<int, ii> pii;

typedef unsigned long long int ull;

int a[MAX], b[MAX], c[MAX], pd[MAX][4], N;



int solve(int i, int op) {

	int &ans = pd[i][op];

	if(i == N) return 0;

	if(ans != -1) return ans;

	int pa = solve(i+1, 1) + a[i];

	int pb = solve(i+1, 2) + b[i];

	int pc = solve(i+1, 3) + c[i];

	if(op == 1) ans = max(pb, pc);

	else if(op == 2) ans = max(pa, pc);

	else if(op == 3) ans = max(pa, pb);

	else ans = max(pa, max(pb, pc));

	return ans;

}



int main(int argc, char** argv) {

	scanf("%d", &N);

	rep(i, 0, N) scanf("%d%d%d", &a[i], &b[i], &c[i]);

	memset(pd, -1, sizeof pd);

	printf("%d\n", solve(0, 0));

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

 

#define REP(i, a, b) for(int i = (a); i <= (b); i++)

#define PER(i, a, b) for(int i = (a); i >= (b); i--)

#define rep(i, a, b) for(int i = (a); i < (b); i++)

#define all(S) (S).begin(), (S).end()

#define pf push_front

#define pb push_back

#define mk make_pair

#define S second

#define F first

typedef long long ll;

typedef long double lf;

typedef pair<int, int> ii;

const int MAX = 1e5+5;

int N, w[MAX][5];

ll pd[MAX][5];



ll solve() {

	REP(i, 1, N) {

		pd[i][1] = max(pd[i-1][2], pd[i-1][3]) + w[i][1];

		pd[i][2] = max(pd[i-1][1], pd[i-1][3]) + w[i][2];

		pd[i][3] = max(pd[i-1][1], pd[i-1][2]) + w[i][3];

	}

	return max(pd[N][1], max(pd[N][2], pd[N][3]));

}



int main(int argc, char ** argv) {

	scanf("%d", &N);

	REP(i, 1, N) REP(j, 1, 3)

		scanf("%d", &w[i][j]);

	printf("%d\n", solve());

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using ll = long long;

using namespace std;



int main() {

  int N,a[100001],b[100001],c[100001];

  cin>>N;

  for (int i(1);i<=N;i++) cin>>a[i]>>b[i]>>c[i];

  ll ans(0);

  ll dp[100001][3]={0};     

  dp[1][0]=a[1];

  dp[1][1]=b[1];

  dp[1][2]=c[1];

  for (int n(2);n<=N;n++){

    dp[n][0]=max(dp[n-1][1]+a[n],dp[n-1][2]+a[n]);

    dp[n][1]=max(dp[n-1][0]+b[n],dp[n-1][2]+b[n]);

    dp[n][2]=max(dp[n-1][0]+c[n],dp[n-1][1]+c[n]);

  }

  cout << max(dp[N][1],max(dp[N][0],dp[N][2]))<<endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using ll = long long;

using namespace std;

ll mod=1e9+7;



int main(){

  int N,a[100000][3];

  cin>>N;

  for (int i(0);i<N;i++) cin>>a[i][0]>>a[i][1]>>a[i][2];

  int dp[100000][3]={0};

  dp[0][0]=a[0][0];

  dp[0][1]=a[0][1];

  dp[0][2]=a[0][2];

  for (int i(0);i<N;i++){

    for (int j(0);j<3;j++){

       for (int k(0);k<3;k++){

         if (j!=k){

           dp[i+1][k]=max(dp[i+1][k],dp[i][j]+a[i+1][k]);

         }

       }

    }

  }

  cout << max(dp[N-1][0],max(dp[N-1][1],dp[N-1][2])) << endl;

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

using ll = long long;

using Graph = vector<vector<int>>;

using pint = pair<int, int>;

int dx[4] = {1, 0, -1, 0};

int dy[4] = {0, 1, 0, -1};

const int MOD = 1000000009;

const long long INF = 1LL << 60;



int main() {

    int N; 

    cin >> N;

    int abc[100010][3]{};

    for (int i = 0; i < N; ++i) for (int j = 0; j < 3; ++j) cin >> abc[i][j];

    int dp[100010][3]{};

    for (int i = 0; i < N; ++i) {

        for (int j = 0; j < 3; ++j) {

            for (int k = 0; k < 3; ++k) {

                if (j == k) continue;

                dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abc[i][k]);

            }

        }

    }

    int res = 0;

    for (int i = 0; i < 3; ++i) res = max(res, dp[N][i]);

    cout << res << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;

using ll = long long;

using Graph = vector<vector<int>>;

using pint = pair<int, int>;

int dx[4] = {1, 0, -1, 0};

int dy[4] = {0, 1, 0, -1};

const int MOD = 1000000007;

const long long INF = 1LL << 60;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



ll abc[100100][3]{};

ll dp[100100][3]{};



int main() {

    int N; cin >> N;

    for (int i = 0; i < N; ++i) for (int j = 0; j < 3; ++j) cin >> abc[i][j];

    for (int a = 0; a < N; ++a) {

        for (int b = 0; b < 3; ++b) {

            for (int c = 0; c < 3; ++c) {

                if (b == c) continue;

                chmax(dp[a+1][c], dp[a][b] + abc[a][c]);

            }

        }

    }

    ll res = 0;

    for (int i = 0; i < 3; ++i) chmax(res, dp[N][i]);

    cout << res << endl;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int n,m,x[15005],y[15005];

bool vis[15005];

vector<int> g[15005];

long long ans;

void dfs(int x)

{

    if(vis[x])

        return;

    vis[x]=1;

    for(int i=0;i<g[x].size();i++)

        dfs(g[x][i]);

}

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    cin>>n>>m;

    for(int i=1;i<=m;i++)

        cin>>x[i]>>y[i];

    for(int i=1;i<=m;i++)

    {

        memset(vis,0,sizeof(vis));

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

            g[j].clear();

        for(int j=1;j<=m;j++)

            if(j!=i)

            {

                g[x[j]].push_back(y[j]);

                g[y[j]].push_back(x[j]);

            }

        int cnt=0;

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

            if(!vis[j])

            {

                dfs(j);

                cnt++;

            }

        if(cnt>1)

            ans++;

    }

    cout<<ans;

    return 0;

}

// Optimized solution to the same problem (faster):
#include"bits/stdc++.h"

using namespace std;

int n,m,a[55],b[55];

bool g[55][55],vis[55];

void dfs(int v)

{

	vis[v]=1;

	for(int i=0;i<n;i++)

	{

		if(g[v][i]==0)

			continue;

		if(vis[i]==1)

			continue;

		dfs(i);

	}

}

int main()

{

	cin>>n>>m;

	for(int i=0;i<m;i++)

	{

		cin>>a[i];

		cin>>b[i];

		a[i]--;

		b[i]--;

		g[a[i]][b[i]]=g[b[i]][a[i]]=1;

	}

	int ans=0;

	for(int i=0;i<m;i++)

	{

		g[a[i]][b[i]]=g[b[i]][a[i]]=0;

		for(int j=0;j<n;j++)

			vis[j]=0;

		dfs(0);

		for(int j=0;j<n;j++)

			if(!vis[j])

			{

				ans++;

				break;

			}

		g[a[i]][b[i]]=g[b[i]][a[i]]=1;

	}

	cout<<ans;

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstring>

#include<cstdio>

#include<iostream>

using namespace std;

int vis[51][51];

int f[101][101];

int a[2555][3];

int ans;

int main(){

   int n,m;ans=0;

   scanf("%d%d",&n,&m);

   for(int i=1;i<=m;i++){

   	  scanf("%d%d",&a[i][1],&a[i][2]);

   }

   for(int i=1;i<=m;i++){

       memset(vis,0x3f3f3f3f,sizeof(vis));

   	   for(int j=1;j<=m;j++){

   	   	  if(j!=i)vis[a[j][1]][a[j][2]]=vis[a[j][2]][a[j][1]]=1;

	   }

	   for(int j=1;j<=n;j++)f[j][j]=0;

	   for(int k=1;k<=n;k++){

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

	   	  	 for(int l=1;l<=n;l++){

	   	  		vis[j][l]=vis[l][j]=min(vis[j][l],vis[j][k]+vis[k][l]);

			 }

		  }

	   }

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

	   	  for(int k=1;k<=n;k++){

	   	  	if(vis[j][k]==0x3f3f3f3f){

	   	  		ans++;goto haha;

			  }

			}

	   }

	   haha:;

   }

   cout<<ans;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int a[105],b[105];

int father[105];

int n,m,s,ans=0;

int find(int x){

    if(father[x]!=x)father[x]=find(father[x]);

    return father[x];

}

void unionn(int x,int y){

    x=find(x);y=find(y);

    father[y]=x;

}

void init(int n){

	for(int i=1;i<=n;i++)father[i]=i;

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d%d",&a[i],&b[i]);

	}

	for(int i=1;i<=m;i++){

		init(n);

		for(int j=1;j<=m;j++){

			if(i!=j){

				unionn(a[j],b[j]);

			}

		}

		s=find(1);

		for(int j=2;j<=n;j++){

			if(find(j)!=s){

				ans++;

				break;

			}

		}

	}

	printf("%d",ans);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N;

	cin >> N;



	int A[1001][1000];

	rep1(i, N) {

		rep(j, N - 1) cin >> A[i][j];

		A[i][N - 1] = 0;

	}



	int k[1001] = {}, k2[1001] = {};

	vector<int> V;

	rep1(i, N) V.pb(i);



	int kotae = 0;

	while (V.size()) {

		kotae++;

		vector<int> kari;

		for (auto v : V) {

			if (k2[v] < kotae) {

				int a = A[v][k[v]];

				if (A[a][k[a]] == v) {

					kari.pb(v);

					k2[v] = kotae;

					kari.pb(a);

					k2[a] = kotae;

				}

			}

		}

		swap(V, kari);

		for (auto v : V) k[v]++;

	}



	int OK = 1;

	rep1(i, N) if (k[i] != N - 1) OK = 0;

	if (OK) co(kotae - 1);

	else co(-1);



	Would you please return 0;

}

// Optimized solution to the same problem (faster):
//ここで手段を選ばないゲスな精神が？



//#include<bits/stdc++.h>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint();



	short A[1001][1000];

	rep1(i, N) {

		rep(j, N - 1) A[i][j] = getint();

		A[i][N - 1] = 0;

	}

	short* k[1001];

	rep1(i, N) k[i] = A[i];

	int k2[1001] = {};

	k2[0] = 1e9;

	int V[2][1001], kazu = N;

	rep1(i, N) V[0][i] = i;



	int kotae = 0;

	while (kazu && kotae < 80000) {

		kotae++;

		int dotti = kotae & 1;

		int kari = 0;

		rep (i, kazu) {

			int v = V[!dotti][i];

			if (k2[v] < kotae) {

				int a = *k[v];

				if (k2[a] < kotae && *k[a] == v) {

					V[dotti][kari++] = v;

					k[v]++;

					k2[v] = kotae;

					V[dotti][kari++] = a;

					k[a]++;

					k2[a] = kotae;

				}

			}

		}

		kazu = kari;

	}



	int OK = 1;

	rep1(i, N) if (k[i] - A[i] != N - 1) OK = 0;

	if (kotae == 80000) printf("%d", N* (N - 1) / 2);

	else if (!OK) printf("-1"); 

	else printf("%d", kotae - 1);



	Would you please return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	int N;

	cin >> N;



	int A[1001][1000];

	rep1(i, N) {

		rep(j, N - 1) cin >> A[i][j];

		A[i][N - 1] = 0;

	}



	int k[1001] = {}, k2[1001] = {};

	vector<int> V;

	rep1(i, N) V.pb(i);



	int kotae = 0;

	while (V.size()) {

		kotae++;

		vector<int> kari;

		for (auto v : V) {

			if (k2[v] < kotae) {

				int a = A[v][k[v]];

				if (A[a][k[a]] == v) {

					kari.pb(v);

					k2[v] = kotae;

					kari.pb(a);

					k2[a] = kotae;

				}

			}

		}

		V = kari;

		for (auto v : V) k[v]++;

	}



	int OK = 1;

	rep1(i, N) if (k[i] != N - 1) OK = 0;

	if (OK) co(kotae - 1);

	else co(-1);



	Would you please return 0;

}

// Optimized solution to the same problem (faster):
//ここで手段を選ばないゲスな精神が？



//#include<bits/stdc++.h>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint();



	short A[1001][1000];

	rep1(i, N) {

		rep(j, N - 1) A[i][j] = getint();

		A[i][N - 1] = 0;

	}

	short* k[1001];

	rep1(i, N) k[i] = A[i];

	int k2[1001] = {};

	k2[0] = 1e9;

	int V[2][1001], kazu = N;

	rep1(i, N) V[0][i] = i;



	int kotae = 0;

	while (kazu && kotae < 80000) {

		kotae++;

		int dotti = kotae & 1;

		int kari = 0;

		rep (i, kazu) {

			int v = V[!dotti][i];

			if (k2[v] < kotae) {

				int a = *k[v];

				if (k2[a] < kotae && *k[a] == v) {

					V[dotti][kari++] = v;

					k[v]++;

					k2[v] = kotae;

					V[dotti][kari++] = a;

					k[a]++;

					k2[a] = kotae;

				}

			}

		}

		kazu = kari;

	}



	int OK = 1;

	rep1(i, N) if (k[i] - A[i] != N - 1) OK = 0;

	if (kotae == 80000) printf("%d", N* (N - 1) / 2);

	else if (!OK) printf("-1"); 

	else printf("%d", kotae - 1);



	Would you please return 0;

}

// Fastest known solution for this problem: