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
.