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`.

Examples

Input

3
2 3
1 3
1 2


Output

3


Input

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


Output

4


Input

3
2 3
3 1
1 2


Output

-1
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeMap;
class Main{


	static final int MOD = 1000000007;


	static ArrayList<ArrayList<Pair>> map;
	static TreeMap<Integer,Integer> ans; 
	static int maxnum;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();

		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

		for(int i = 0;i < n;i++){
			list.add(new ArrayList<Integer>());
			for(int j = 0;j < n-1;j++){
				int a = sc.nextInt()-1;
				list.get(i).add(a);
			}
		}
	

		int count = 0;				//終わった試合数のカウント
		int ans = 1;

		Queue<Pair> queue = new LinkedList<Pair>();
		HashSet<Integer> used = new HashSet<Integer>();

		for(int i = 0;i < n;i++){
			int rival = list.get(i).get(0);
			if(list.get(rival).get(0) == i && i < rival && !used.contains(i) && !used.contains(rival)){
				Pair pair = new Pair(i, rival);
				queue.add(pair);
				used.add(i);
				used.add(rival);
				count++;
			}
		}


		while(true){
			Queue<Pair> nextque = new LinkedList<Pair>();
			boolean vail = false;				//行える試合があるか確認

			for(Pair pair:queue){
				
				int first = pair.from;
				int second = pair.end;
				
				list.get(first).remove(0);
				list.get(second).remove(0);
				
				
				if(list.get(first).size() != 0){
					int candidatefirst = list.get(first).get(0);
					if(list.get(candidatefirst).size()!= 0 && list.get(candidatefirst).get(0) == first){
						Pair next = new Pair(first, candidatefirst);
						nextque.add(next);						
						vail = true;
						count++;
					}
				}
				
				if(list.get(second).size() != 0){
					int candidatesecond = list.get(second).get(0);
					if(list.get(candidatesecond).size()!= 0 && list.get(candidatesecond).get(0) == second){
						Pair next = new Pair(second, candidatesecond);
						nextque.add(next);
						vail = true;
						count++;
					}
				}



			}

			ans++;
			
			if(!vail){					//行える試合があるか確認
				System.out.println(-1);
				return;
			}
			
			if(count >= n*(n-1)/2){		
				break;
			}
			queue = nextque;			//更新

		}
		
		
		
		System.out.println(ans);




	}





	static int upperbond(int k,int min,int[] data){		//kより小さい最大の値をdataの中から探し、返す二分探索
		int max = data.length;
		//		if(min == data.length-1){
		//			if(data[min] > k){
		//				return min;
		//			}
		//		}

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}

		return max;
	}

	static int lowerbond(int k,int min,int[] data){		//kより大きい最小の値をdataの中から探し、返す二分探索
		int max = data.length;

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}
		return min;
	}



	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}
	static long gcd(long a,long b){
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}



	static long lcm (long a, long b) {
		long g = gcd(a,b);
		return a/g*b;
	}




}

class Town{
	int index;
	int x ;
	int y;
	public Town(int index,int x,int y) {
		this.index = index;
		this.x = x;
		this.y = y;
		// TODO 自動生成されたコンストラクター・スタブ
	}


}


class Edge  implements Comparable{

	int index;
	HashSet<Integer> hen;
	HashSet<Integer> used;
	HashMap<Integer, Integer> map;
	int size;


	public Edge(int index) {
		// TODO 自動生成されたコンストラクター・スタブ
		this.index = index;
		hen = new HashSet();
		used = new HashSet<Integer>();
		map = new HashMap<Integer,Integer>();
	}

	public int compareTo(Object other) {
		Edge otherpair = (Edge)other;

		return   otherpair.hen.size() - hen.size();
	}
}

class Food implements Comparable{

	int minits;
	int score;
	double cospa;

	public Food(int from,int end,double c) {
		this.minits = from;
		this.score = end;
		this.cospa = c;
		// TODO 自動生成されたコンストラクター・スタブ
	}

	@Override
	public int compareTo(Object other) {
		Food otherpair = (Food)other;
		int dif = Double.compare(otherpair.cospa, cospa);
		return   dif;
	}

}

class Pair implements Comparable{
	int from;
	int end;
	public Pair(int from,int end) {
		this.from = from;
		this.end = end;
		// TODO 自動生成されたコンストラクター・スタブ
	}

	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return  from - otherpair.from;
	}








}




