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 <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

struct Amida {
	int p1, p2, p3;
};
bool operator== (const Amida &a1, const Amida &a2) {
	if (a1.p1 == a2.p1 && a1.p2 == a2.p2 && a1.p3 == a2.p3) return true;
	return false;
}
bool operator<(const Amida &a1, const Amida &a2) {
	if (a1.p1 < a2.p1) return true; if (a1.p1 > a2.p1) return false;
	if (a1.p2 < a2.p2) return true; if (a1.p2 > a2.p2) return false;
	if (a1.p3 < a2.p3) return true; if (a1.p3 > a2.p3) return false;
	return false;
}

int n, w[109], c[109]; vector<int>a[109]; Amida S[109];
vector<Amida>I;

Amida solve(vector<int>v) {
	Amida F = Amida{ 1,2,3 };
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == 0) swap(F.p1, F.p2);
		if (v[i] == 1) swap(F.p2, F.p3);
	}
	return F;
}
Amida gousei(Amida P1, Amida P2) {
	int r[3] = { 0,0,0 }, q[3] = { P1.p1,P1.p2,P1.p3 };
	r[0] = q[P2.p1 - 1];
	r[1] = q[P2.p2 - 1];
	r[2] = q[P2.p3 - 1];
	return Amida{ r[0],r[1],r[2] };
}
Amida toAmida(int p) {
	if (p == 0) return Amida{ 1,2,3 };
	if (p == 1) return Amida{ 1,3,2 };
	if (p == 2) return Amida{ 2,1,3 };
	if (p == 3) return Amida{ 2,3,1 };
	if (p == 4) return Amida{ 3,1,2 };
	if (p == 5) return Amida{ 3,2,1 };
}
int toNumber(Amida P) {
	if (P == Amida{ 1, 2, 3 }) return 0;
	if (P == Amida{ 1, 3, 2 }) return 1;
	if (P == Amida{ 2, 1, 3 }) return 2;
	if (P == Amida{ 2, 3, 1 }) return 3;
	if (P == Amida{ 3, 1, 2 }) return 4;
	if (P == Amida{ 3, 2, 1 }) return 5;
}

bool solve(vector<Amida>Z) {
	Amida ZZ = Amida{ 1,2,3 };

	for (int i = 0; i < Z.size(); i++) {
		ZZ = gousei(ZZ, Z[i]);
		if (ZZ == Amida{ 1,2,3 }) return true;
	}
	return false;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> w[i];
		for (int j = 0; j < w[i]; j++) {
			int p; cin >> p;
			a[i].push_back(p);
		}
		S[i] = solve(a[i]);
		c[toNumber(S[i])]++;
	}
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < min(2, c[i]); j++) I.push_back(toAmida(i));
	}

	if (n != I.size()) {
		cout << "yes" << endl;
	}
	else {
		bool flag = false;
		do {
			if (solve(I) == true) {
				flag = true;
				break;
			}
		} while (next_permutation(I.begin(), I.end()));

		if (flag == true) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}