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
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return a > val ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
struct matrix {
  static const int MAXN = 100;
  static const int MOD = (int)1e9 + 7;
  int x[MAXN][MAXN];
  matrix() { memset(x, 0, sizeof(x)); }
  matrix unit() {
    matrix res;
    for (int i = 0; i < MAXN; i++) res.x[i][i] = 1;
    return res;
  }
  matrix operator+(matrix A) {
    matrix res;
    for (int i = 0; i < MAXN; i++)
      for (int j = 0; j < MAXN; j++) {
        res.x[i][j] = x[i][j] + A.x[i][j];
        if (res.x[i][j] >= MOD) res.x[i][j] -= MOD;
      }
    return res;
  }
  matrix operator*(matrix A) {
    matrix res;
    for (int i = 0; i < MAXN; i++)
      for (int k = 0; k < MAXN; k++)
        for (int j = 0; j < MAXN; j++) {
          res.x[i][j] = (res.x[i][j] + (long long)x[i][k] * A.x[k][j]) % MOD;
        }
    return res;
  }
  matrix operator^(long long k) {
    if (!k) return unit();
    matrix res, tmp;
    for (int i = 0; i < MAXN; i++)
      for (int j = 0; j < MAXN; j++) {
        res.x[i][j] = tmp.x[i][j] = x[i][j];
      }
    k--;
    while (k) {
      if (k & 1) res = res * tmp;
      tmp = tmp * tmp;
      k >>= 1;
    }
    return res;
  }
  friend matrix sumpower(matrix A, long long k) {
    if (k == 1) return A;
    vector<int> bit;
    while (k) {
      bit.push_back(k & 1);
      k >>= 1;
    }
    matrix res = A, tmp = A;
    for (int i = bit.size() - 2; i >= 0; i--) {
      res = res + (res * tmp);
      tmp = tmp * tmp;
      if (bit[i] & 1) {
        tmp = tmp * A;
        res = res + tmp;
      }
    }
    return res;
  }
};
const int maxn = 2010;
int n;
int a[maxn][maxn];
vector<int> adj[maxn];
vector<int> radj[maxn];
int vis[maxn];
vector<int> VS;
void dfs1(int u) {
  vis[u] = 1;
  for (int i = (0); i < (int((adj[u]).size())); i++) {
    int v = adj[u][i];
    if (!vis[v]) {
      dfs1(v);
    }
  }
  VS.push_back(u);
}
void dfs2(int u) {
  vis[u] = 1;
  for (int i = (0); i < (int((radj[u]).size())); i++) {
    int v = radj[u][i];
    if (!vis[v]) {
      dfs2(v);
    }
  }
}
void solve() {
  scanf("%d", &n);
  for (int i = (0); i < (n); i++)
    for (int j = (0); j < (n); j++) {
      scanf("%d", &a[i][j]);
      if (a[i][j]) {
        adj[i].push_back(j);
        radj[j].push_back(i);
      }
    }
  dfs1(0);
  for (int i = (0); i < (n); i++) {
    if (!vis[i]) {
      cout << "NO\n";
      return;
    }
  }
  memset(vis, 0, sizeof(vis));
  dfs2(VS.back());
  for (int i = (0); i < (n); i++) {
    if (!vis[i]) {
      cout << "NO\n";
      return;
    }
  }
  cout << "YES\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}
