Island Memories

Time limit3sMemory limit2048 MB

Summary

Given n islands and m remembered zones, decide whether some tree on the islands exists where each zone is exactly the component left after removing one edge.

Level: Medium7 of 10
Topics: Tree, Divide and conquer, Implementation
Solved: No attempts yet

Problem

There is an island country that has $n$ islands numbered $1$ to $n$ . The islands are connected by $n - 1$ bidirectional drawbridges, such that it is possible to travel from each island to every other island. Every drawbridge can be lifted to provide clearance for boat traffic. Sometimes a drawbridge can be lifted for a prolonged period of time, during which the country operates as two zones of road traffic. Each zone is a maximal set of islands connected by the un-lifted drawbridges. It is impossible to travel by road from one zone to the other zone. The country never lifts more than one drawbridge at any time in order to mitigate the inconvenience of road travel.

You are writing a tourist guide for people who would like to visit this island country. The country does not yet have a map that describes how its islands are connected by drawbridges. You interviewed $m$ islanders who live in this country. Each islander told you a memory that describes which islands were in their zone at some time in the past when a drawbridge was lifted. However, some islanders might have remembered things wrong. You want to check whether all the islanders' memories are consistent. The memories are consistent if there is a way to connect the islands by drawbridges so that every zone described by the $m$ islanders can be formed by lifting exactly one drawbridge at a time.

Input

The first line has two integers $n$ , $m$ ( $2 \le n, m \le 1000$ ), the number of islands in the country and the number of islanders you interviewed.

This is followed by $m$ islanders' memories. Each memory starts with a single integer $k$ ( $1 \le k < n$ ) on its own line, the number of islands in that islander's zone. The next line has $k$ integers in increasing order giving those islands in the zone. You may assume that the islanders never left out any islands in their zone when describing their memories, so each set of islands is maximal when connected by the un-lifted drawbridges.

Output

Output $1$ if all the islanders' memories are consistent, or $0$ otherwise.

Examples3

Example 1
Input
```
5 2
2
1 2
3
1 2 3
```
Expected output
```
1
```
Example 2
Input
```
5 2
2
1 4
3
1 2 4
```
Expected output
```
1
```
Example 3
Input
```
5 2
2
1 2
2
1 3
```
Expected output
```
0
```