Link with Level Editor I
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

Please pay attention to the unusual memory limit.

Link is playing a game, called NIO's Game.

In this game, a level consists of several worlds. Each world consists of m nodes and some directed roads. The player starts on node 1 of the first world. In each world, the player can either stay at current node or go through exactly one road that exists in that world. After that, the player will be teleported to the next world without changing the ID of the node where he stays. If there is no next world, the game ends. The player wins if he ends on node m.

Link is editing a new level, he has already made n worlds (numbered from 1 to n) and wants to choose a continuous subsegment of them to form a new level. The only limit is that there should be at least one way to win.

Link doesn't want to use too many worlds. What is the minimum number of worlds Link needs to use in the new level?

输入描述:

The first line contains two integers n,m ().

The following input describes the worlds numbered from 1 to n. For each world:

The first line contains an integer l (), which is the number of roads in this world.

In the next l lines, each line contains two integers u,v (), which means there is a road from node u to node v in this world.

For each world, it is guaranteed that there is no duplicate edge.

For each test point, it is guaranteed that the sum of l does not exceed .

输出描述:

Output a single integer, which is the minimum number of worlds Link needs to use in the new level. If Link couldn't make such a level, output -1.
示例1

输入

复制
3 3
1
2 1
1
2 3
1
1 2

输出

复制
-1
示例2

输入

复制
3 3
1
2 1
1
1 2
1
2 3

输出

复制
2