You have matrix a of size n × n. Let's number the rows of the matrix from 1 to n from top to bottom, let's number the columns from 1 to n from left to right. Let's use aij to represent the element on the intersection of the i-th row and the j-th column. 

Matrix a meets the following two conditions: 

  * for any numbers i, j (1 ≤ i, j ≤ n) the following inequality holds: aij ≥ 0; 
  * <image>. 



Matrix b is strictly positive, if for any numbers i, j (1 ≤ i, j ≤ n) the inequality bij > 0 holds. You task is to determine if there is such integer k ≥ 1, that matrix ak is strictly positive.

Input

The first line contains integer n (2 ≤ n ≤ 2000) — the number of rows and columns in matrix a.

The next n lines contain the description of the rows of matrix a. The i-th line contains n non-negative integers ai1, ai2, ..., ain (0 ≤ aij ≤ 50). It is guaranteed that <image>.

Output

If there is a positive integer k ≥ 1, such that matrix ak is strictly positive, print "YES" (without the quotes). Otherwise, print "NO" (without the quotes). 

Examples

Input

2
1 0
0 1


Output

NO


Input

5
4 5 6 1 2
1 2 3 4 5
6 4 1 2 4
1 1 1 1 1
4 4 4 4 4


Output

YES
//Author: net12k44
import java.io.*;
import java.util.*;
//public
class Main{//}
int nn, n;
ArrayDeque<Integer> S;
int a[][], low[] , num[] , v[];

private void dfs(int i){
	low[i] = num[i] = ++nn;
	S.push(i);
	for(int j = 0; j < n; ++j)
		if (a[i][j] > 0 && v[j] == -1){
			if (low[j] > 0) low[i] = Math.min(low[i] , num[j]); 
			else {
				dfs(j);
				low[i] = Math.min(low[i] , low[j]);
			}		
		}
		
	if (low[i] != num[i]) return;
	while (true){
		int j = S.pop();
		v[j] = i;
		if (i == j) return;
	}
}

private void solve() {
	n = in.nextInt(); nn = 0;
	a = new int[n][n];
	for(int i = 0; i < n; ++i)
	for(int j = 0; j < n; ++j) a[i][j] = in.nextInt();
	
	low = new int[n]; num = new int[n]; v = new int[n];
	Arrays.fill(v , -1); S = new ArrayDeque<Integer>();
	dfs(0);
	for(int i = 0; i < n; ++i)
		if (v[i] != 0) {
			out.println("NO");
			return;
		}
	out.println("YES");		
}
    
public static void main (String[] args) throws java.lang.Exception {        
    long startTime = System.currentTimeMillis();

    out = new PrintWriter(System.out);
    new Main().solve();    
    //out.println((String.format("%.2f",(double)(System.currentTimeMillis()-startTime)/1000)));
    out.close();
}

static PrintWriter out;    
static class in {
    static BufferedReader reader = new BufferedReader( new InputStreamReader(System.in) ) ;
    static StringTokenizer tokenizer = new StringTokenizer("");             
    static String next() {      
        while ( !tokenizer.hasMoreTokens() )
            try { tokenizer = new StringTokenizer( reader.readLine() ); }
            catch (IOException e){
                throw new RuntimeException(e);          
            }       
        return tokenizer.nextToken();
    }
    static int nextInt() { return Integer.parseInt( next() ); }     
    static long nextLong(){ return Long.parseLong( next() ); }
}
//////////////////////////////////////////////////
}//
