Problem: Problem

There are $ N $ Amidakuji with 3 vertical lines.
No matter which line you start from, the Amidakuji that ends at the starting line is considered a good Amidakuji.
You can select one or more Amidakuji and connect them vertically in any order.
Output "yes" if you can make a good Amidakuji, otherwise output "no".

There are $ w_i $ horizontal lines in the $ i $ th Amidakuji.
$ a_ {i, j} $ indicates whether the $ j $ th horizontal bar from the top of Amidakuji $ i $ extends from the central vertical line to the left or right.
If $ a_ {i, j} $ is 0, it means that it extends to the left, and if it is 1, it means that it extends to the right.

Constraints

The input satisfies the following conditions.

* $ 1 \ le N \ le 50 $
* $ 0 \ le w_i \ le 100 $
* $ a_ {i, j} $ is 0 or 1

Input

The input is given in the following format.


$ N $
$ w_1 $ $ a_ {1,1} $ $ a_ {1,2} $ ... $ a_ {1, w_1} $
$ w_2 $ $ a_ {2,1} $ $ a_ {2,2} $ ... $ a_ {2, w_2} $
...
$ w_N $ $ a_ {N, 1} $ $ a_ {N, 2} $ ... $ a_ {N, w_N} $


All inputs are given as integers.
$ N $ is given on the first line.
$ W_i $ and $ w_i $ $ a_ {i, j} $ are given on the following $ N $ line, separated by blanks.

Output

If you can make a good Amidakuji, it outputs "yes", otherwise it outputs "no".

Examples

Input

3
2 0 0
1 1
5 1 0 0 1 0


Output

yes


Input

2
1 1
1 0


Output

no

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

int main() {
  int n;

  cin >> n;

  vector<vector<int>> v;
  v.resize(n);
  for(int i = 0; i < n; i++){
    int w;
    cin >> w;

    v[i].push_back(1);
    v[i].push_back(2);
    v[i].push_back(3);
    for(int j = 0; j < w; j++){
      int a;
      cin >> a;
      if(a == 0){
        if(v[i][0] == 1){
          v[i][0] = 2;
        }
        else if(v[i][0] == 2){
          v[i][0] = 1;
        }
        if(v[i][1] == 1){
          v[i][1] = 2;
        }
        else if(v[i][1] == 2){
          v[i][1] = 1;
        }
        if(v[i][2] == 1){
          v[i][2] = 2;
        }
        else if(v[i][2] == 2){
          v[i][2] = 1;
        }
      }
      else{
        if(v[i][0] == 2){
          v[i][0] = 3;
        }
        else if(v[i][0] == 3){
          v[i][0] = 2;
        }
        if(v[i][1] == 2){
          v[i][1] = 3;
        }
        else if(v[i][1] == 3){
          v[i][1] = 2;
        }
        if(v[i][2] == 2){
          v[i][2] = 3;
        }
        else if(v[i][2] == 3){
          v[i][2] = 2;
        }
      }
    }
  }

  int cnt[3]={0,0,0};
  rep(i,n){
    if(v[i][0] == 1 && v[i][1] == 2 && v[i][2] == 3){
      cout << "yes" << endl;
      return 0;
    }
    if(v[i][0]==1&&v[i][1]!=2)cnt[0]++;
    if(v[i][1]==2&&v[i][2]!=3)cnt[1]++;
    if(v[i][2]==3&&v[i][0]!=1)cnt[2]++;
  }
  rep(j,3){
    if(cnt[j]>=2){
      cout<<"yes"<<endl;
      return 0;
    }
  }

  int cnt2[2]={0,0};
  rep(i,n){
    if(v[i][0] == 2 && v[i][1] == 3 && v[i][2] == 1){
      cnt2[0]++;
    }
    if(v[i][0] == 3 && v[i][1] == 1 && v[i][2] == 2){
      cnt2[1]++;
    }
  }
  rep(j,2){
    if(cnt[j]>=3){
      cout<<"yes"<<endl;
      return 0;
    }
  }

  vector<int> idx;
  rep(i,n)idx.push_back(i);

  do{
    vector<int> y = {1, 2, 3}, tmp = {0, 0, 0};
    rep(i,n){
      int j=idx[i];
      tmp[v[j][0]-1] = y[0];
      tmp[v[j][1]-1] = y[1];
      tmp[v[j][2]-1] = y[2];
      if(tmp[0] == 1 && tmp[1] == 2 && tmp[2] == 3){
        cout << "yes" << endl;
        return 0;
      }
      else{
        y[0] = tmp[0];
        y[1] = tmp[1];
        y[2] = tmp[2];
      }
    }
  }while(next_permutation(all(idx)));

  cout<<"no"<<endl;

  return 0;
}