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;
#define mod 1000000007
using ll = long long;
int dd[] = { 0, 1, 0, -1, 0 }; //→↓←↑

void solve()
{
	int N;
	cin >> N;
	vector<int>W(N);
	//using T = tuple<int, int, int>;
	vector<vector<int>> V(N);

	for (int i = 0; i < N; i++)
	{
		cin >> W[i];
		vector<int> A(W[i]);
		for (int j = 0; j < W[i]; j++)
		{
			cin >> A[j];
		}
		V[i].push_back(0);
		V[i].push_back(1);
		V[i].push_back(2);
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < W[i]; k++)
			{
				if (A[k] == 0)
				{
					if (V[i][j] == 1)V[i][j] = 0;
					else if (V[i][j] == 0)V[i][j] = 1;
				}
				else
				{
					if (V[i][j] == 1)V[i][j] = 2;
					else if (V[i][j] == 2) V[i][j] = 1;
				}
				//cout << A[k] << " " << V[i][j]  << endl;
			}
		}
		//cout << V[i][0] << " " << V[i][1] << " " << V[i][2] << endl;
	}

	int n2 = N / 2;
	vector<int> tmp(3);
	vector<vector<int>> P(1 << n2);
	bool B[3][3][3];
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				B[i][j][k] = false;
			}
		}
	}
	for (int i = 1; i < 1 << n2; i++)
	{
		P[i].push_back(0);
		P[i].push_back(1);
		P[i].push_back(2);
		for (int j = 0; j < n2; j++)
		{
			if (i >> j & 1) //jを使う
			{
				tmp[0] = P[i][0];
				tmp[1] = P[i][1];
				tmp[2] = P[i][2];
				P[i][0] = tmp[V[j][0]];
				P[i][1] = tmp[V[j][1]];
				P[i][2] = tmp[V[j][2]];
			}
		}
		if (P[i][0] == 0 && P[i][1] == 1 && P[i][2] == 2)
		{
			cout << "yes" << endl;
			return;
		}
		B[P[i][0]][P[i][1]][P[i][2]] = true;
	}


	for (int i = 1; i < 1 << (N - n2); i++)
	{
		vector<int> Q;
		Q.push_back(0);
		Q.push_back(1);
		Q.push_back(2);

		for (int j = 0; j < N - n2; j++)
		{
			if (i >> j & 1)
			{
				tmp[0] = Q[0];
				tmp[1] = Q[1];
				tmp[2] = Q[2];
				//cout << Q[0] << " " << Q[1] << " " << Q[2] << endl;
				Q[0] = tmp[V[j + n2][0]];
				Q[1] = tmp[V[j + n2][1]];
				Q[2] = tmp[V[j + n2][2]];
				//cout << Q[0] << " " << Q[1] << " " << Q[2] << endl;
			}
		}

		if (Q[0] == 0 && Q[1] == 1 && Q[2] == 2)
		{
			cout << "yes" << endl;
			return;
		}
		//cout << Q[0] << " " << Q[1] << " " << Q[2] << endl;
		int zero, one, two;
		for (int k = 0; k < 3; k++)
		{
			if (Q[k] == 0)
			{
				zero = k;
			}
			if (Q[k] == 1)
			{
				one = k;
			}
			if (Q[k] == 2)
			{
				two = k;
			}
		}
		if (B[zero][one][two])
		{
			cout << "yes" << endl;
			return;
		}
	}

	cout << "no" << endl;



}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	return 0;
}