Gnomes

Time limit1sMemory limit512 MB

Summary

Find the earliest hour when a token starting at station 1 can reach station n using swaps within unwatched stations each hour.

Level: Hard8 of 10
Topics: BFS, Graph
Solved: No attempts yet

Statement

The wicked dragon Bitol invaded the land of the gnomes and enslaved its inhabitants. He assigned each of the $n$ gnomes a different workstation and then, sprawled on a heap of stolen treasure, lazily oversees their toil.

Because Bitol is an exceptionally slothful dragon, he does not watch all of his subjects at once. Instead he keeps a close eye only on the gnomes working at a certain group of stations at any given time. While he is looking away, all the gnomes he is not watching may meet one another and swap places freely (Bitol cannot remember which gnome worked at which station). Every hour the dragon turns his head and begins watching a different group of gnomes.

Bajtazyl, the gnome assigned station $1$ , wants to rally his fellow captives against Bitol. To do so he must first meet the venerable gnome Bajtomir, who was assigned station $n$ . Bajtazyl therefore faces a challenge: by swapping places with other gnomes at the right moments, he must, as quickly as possible, bring about a situation in which neither the station he is currently standing at nor station $n$ is being watched by the dragon.

Your task is to determine the earliest moment at which this meeting can take place. Fortunately, it is known that after $m$ hours Bitol will fall asleep, and from then on all the gnomes will be able to communicate freely.

Input

The first line of standard input contains two integers $n$ and $m$ ( $1 \le n, m \le 1\,000\,000$ ), the number of gnomes and the number of hours remaining until Bitol falls asleep. Each of the next $m$ lines describes the group of stations watched by the dragon during one hour. The description of the $i$ -th group consists of an integer $k_i$ ( $1 \le k_i \le n$ ), the number of watched stations, followed by $k_i$ integers from $\{1, \dots, n\}$ in increasing order, the numbers of the watched stations. All numbers on a line are separated by single spaces.

You may assume that $k_1 + k_2 + \dots + k_m \le 2\,000\,000$ .

Output

Print a single integer from $\{0, \dots, m\}$ : the smallest number of hours after which Bajtazyl can reach Bajtomir.

Explanation

Explanation of the examples

In the first example, during the first hour of his journey Bajtazyl cannot leave station $1$ , because it is being watched by the dragon. During the second hour he can swap places with the gnome at station $4$ . Thanks to this, only at the start of the third hour does Bitol turn his head toward stations $1$ , $2$ , and $3$ , and Bajtazyl is finally able to meet Bajtomir.

In the second example, the meeting can happen immediately, because during the first hour the dragon is not looking at either Bajtazyl's or Bajtomir's station.

In the third example, the meeting can happen only once Bitol falls asleep.

Examples3

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

Example 3

Input

10 4
1 1
2 9 10
7 1 3 4 7 8 9 10
2 1 10

Expected output