题目描述

有一个岛国，共有 $n$ 个岛屿，编号为 $1$ 到 $n$。这些岛屿之间通过恰好 $n-1$ 座双向吊桥连接，并且任意两个岛屿之间都能够互相到达。因此，所有岛屿和吊桥构成一棵树。

每座吊桥都可以升起，以便船只通行。当某一座吊桥在较长时间内保持升起状态时，整个国家会被分成两个无法通过道路互相到达的区域。每个区域都是由仍未升起的吊桥连接起来的一个极大岛屿集合。为了尽量减少对道路交通的影响，任意时刻最多只会升起一座吊桥。

你正在编写这个岛国的旅游指南，但当地并没有现成的吊桥连接地图。于是你采访了 $m$ 位岛民。每位岛民都回忆起过去某次有一座吊桥升起时，自己所在区域中包含哪些岛屿。

不过，一些岛民的记忆可能并不正确。请判断所有这些记忆是否能够同时成立。

具体来说，你需要判断是否存在一种用 $n-1$ 座吊桥连接这 $n$ 个岛屿的方式，使得对于每一位岛民所描述的岛屿集合，都存在某一座吊桥，删除这座桥后，该集合恰好成为产生的两个连通块之一。

输入格式

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

接下来依次给出 $m$ 位岛民的记忆。

对于每位岛民：

• 第一行包含一个整数 $k$，其中 $1\le k<n$，表示该岛民记忆中的区域包含 $k$ 个岛屿；
• 第二行包含 $k$ 个严格递增的整数，表示这些岛屿的编号。

保证每位岛民都完整地给出了其所在区域中的所有岛屿，也就是说，他所描述的集合应当对应删除一座吊桥后得到的一个完整连通块，而不是其中的一部分。

输出格式

如果存在一种吊桥连接方式，使所有岛民的记忆都能够成立，输出：

1

否则输出：

0

样例 1

输入

5 2
2
1 2
3
1 2 3

输出

1

样例 2

输入

5 2
2
1 4
3
1 2 4

输出

1

样例 3

输入

5 2
2
1 2
2
1 3

输出

0