有一个岛国，拥有 $n$ 个岛屿，编号为 $1$ 到 $n$。这些岛屿由 $n - 1$ 座双向吊桥连接，使得从任意一个岛屿都可以到达其他所有岛屿。

每座吊桥都可以升起以允许船只通行。有时，某座吊桥会升起较长一段时间，在此期间，该国会被分割为两个陆路交通区域。每个区域都是由未升起的吊桥连接的岛屿的极大集合。此时，无法通过陆路从一个区域前往另一个区域。为了减少陆路交通的不便，该国在任何时候最多只会升起一座吊桥。

你正在为想要访问这个岛国的游客编写一本旅游指南。你发现该国目前还没有一张描述岛屿之间如何通过吊桥连接的地图。因此，你采访了居住在该国的 $m$ 位岛民以获取一些信息。每位岛民都向你讲述了一段回忆，描述了过去某个时刻当有一座吊桥升起时，他们所在的区域包含哪些岛屿。然而，有些岛民可能会记错。你想检查所有岛民的回忆是否是一致的，即是否存在一种用吊桥连接岛屿的方式，使得在每次只升起一座吊桥时，这 $m$ 位岛民所描述的区域都能实际形成。

输入格式

第一行包含两个整数 $n, m$（$2 \le n, m \le 1000$），分别表示该国的岛屿数量和接受采访的岛民数量。

接下来是 $m$ 个岛民的回忆。每个岛民的回忆第一行包含一个整数 $k$（$1 \le k < n$），表示该岛民所在区域的岛屿数量。

下一行包含 $k$ 个按升序排列的整数，表示该区域内的岛屿编号。你可以认为岛民在描述他们的回忆时从未遗漏过其所在区域的任何岛屿（即回忆中的岛屿集合是由未升起的吊桥连接的极大集合）。

输出格式

如果所有岛民的回忆是一致的，则输出 1，否则输出 0。

样例

输入样例 1

5 2
2
1 2
3
1 2 3

输出样例 1

1

输入样例 2

5 2
2
1 4
3
1 2 4

输出样例 2

1

输入样例 3

5 2
2
1 2
2
1 3

输出样例 3

0