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
import java.awt.Point;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Currency;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * @author Jens Staahl
 */

public class Prac {

	// some local config
	// static boolean test = false ;
	private boolean test = System.getProperty("ONLINE_JUDGE") == null;
	static String testDataFile = "testdata.txt";
	// static String testDataFile = "testdata.txt";
	private static String ENDL = "\n";
	// Just solves the acutal kattis-problem
	ZKattio io;
	int maxn = (int)Math.sqrt((int) (1e9));

	boolean addZeroes = false;

	int[] num, lowlink, comp;
	Stack<Integer> stack;
	// List<Integer>[] edges;
	int no_vert, no_comp;
	
	private void solve() throws Throwable {
		io = new ZKattio(stream);
		long t0 = System.currentTimeMillis();
		int n = io.getInt();
		List[] edges = new List[n];
		
		num = new int[n];
		lowlink = new int[n];
		comp = new int[n];
		Arrays.fill(comp, -1);
		stack = new Stack<Integer>();
		no_vert = 0;
		no_comp = 0;
		

		
		for (int i = 0; i < n; i++) {
			edges[i] = new ArrayList<>();
		}
		int start = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int val = io.getInt();
				if( i== j && val > 0){
					start = i;
				}
				if(val > 0) {
					edges[i].add(j);
				}
			}
		}

		tarjan(0, edges);
		boolean ok = true;
		for (int i = 0; i < comp.length; i++) {
			if(comp[i] != 0) {
				ok = false;
			}
		}
		
		if(ok) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
		if(test) {
			System.out.println(System.currentTimeMillis() - t0);
		}

	}
	private void tarjan(int v, List[] edges) {
		num[v] = no_vert;
		no_vert++;
		lowlink[v] = num[v];

		comp[v] = Integer.MAX_VALUE / 2;
		stack.push(v);
		for (int i = 0; i < edges[v].size(); i++) {
			int w = (Integer) edges[v].get(i);
			if (comp[w] == -1) {
				tarjan(w, edges);
				lowlink[v] = Math.min(lowlink[w], lowlink[v]);
			} else if (comp[w] == Integer.MAX_VALUE / 2) {
				lowlink[v] = Math.min(num[w], lowlink[v]);
			}
		}
		if (lowlink[v] == num[v]) {
			while (true) {
				int x = stack.pop();
				comp[x] = no_comp;
				if (x == v) {
					no_comp++;
					break;
				}
			}

		}

	}


	private boolean check(List[] edges, int start, boolean[] visited) {
		Stack<Integer> stack = new Stack<>();
		stack.push(start);
		while(stack.size() > 0) {
			Integer node = stack.pop();
			List<Integer> nodes = edges[node];
			for (int i = 0; i < nodes.size(); i++) {
				Integer to = nodes.get(i);
				if(!visited[to]) {
					stack.push(to);
					visited[to] = true;
				}
			}
		}
//		boolean ok = true;
		for (int i = 0; i < visited.length; i++) {
			if(!visited[i]) {
				return false;
//				ok = false;
			}
		}
		return true;
	}

	public static void main(String[] args) throws Throwable {
		new Prac().solve();
	}

	public Prac() throws Throwable {
		if (test) {
			stream = new FileInputStream(testDataFile);
		}
	}

	InputStream stream = System.in;
	PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));// outStream

	public class ZKattio extends PrintWriter {
		public ZKattio(InputStream i) {
			super(new BufferedOutputStream(System.out));
			r = new BufferedReader(new InputStreamReader(i));
		}

		public ZKattio(InputStream i, OutputStream o) {
			super(new BufferedOutputStream(o));
			r = new BufferedReader(new InputStreamReader(i));
		}

		public boolean hasMoreTokens() {
			return peekToken() != null;
		}

		public int getInt() {
			return Integer.parseInt(nextToken());
		}

		public double getDouble() {
			return Double.parseDouble(nextToken());
		}

		public long getLong() {
			return Long.parseLong(nextToken());
		}

		public String getWord() {
			return nextToken();
		}

		private BufferedReader r;
		private String line;
		private StringTokenizer st;
		private String token;

		private String peekToken() {
			if (token == null)
				try {
					while (st == null || !st.hasMoreTokens()) {
						line = r.readLine();
						if (line == null)
							return null;
						st = new StringTokenizer(line);
					}
					token = st.nextToken();
				} catch (IOException e) {
				}
			return token;
		}

		private String nextToken() {
			String ans = peekToken();
			token = null;
			return ans;
		}
	}
	// System.out;

}