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 nodes and some directed roads. The player starts on node 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 .

Link is editing a new level, he has already made worlds (numbered from to ) 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  ().

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

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

In the next  lines, each line contains two integers  (), which means there is a road from node  to node  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  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 .

3 3
1
2 1
1
2 3
1
1 2

-1

3 3
1
2 1
1
1 2
1
2 3

2