Minimum Bus Transfers

H City is a popular tourist destination with thousands of visitors each year. To help tourists get around, a bus company has set up bus stops near various tourist attractions, hotels, and restaurants, and operates a number of one‐way bus routes. Each bus route starts at one bus stop, passes through several stops in sequence, and finally reaches its terminal stop.

A traveler staying at a hotel (located at bus stop 1) wants to visit S Park (located at bus stop (N)). If there is no single bus route that goes directly from the hotel to S Park, the traveler may ride one bus for several stops, then transfer at a stop to another bus, and so on until S Park is reached. The goal is to find an optimal travel plan which minimizes the number of bus transfers (i.e. the number of times the traveler has to change buses).

Formally, the bus stops in H City are numbered (1, 2, \dots, N), where 1 is the hotel and (N) is S Park. There are (M) one‐way bus routes. Each bus route is given as a sequence of stops. A traveler can board a bus route at stop (s) if the route includes (s), and can only ride that route to stops that appear after (s) in its sequence. The traveler may transfer between bus routes at any stop (provided that the bus route being transferred to contains that stop and can take the traveler further along).

If the traveler can directly ride a single bus from stop 1 to stop (N), then no transfers are required. Otherwise, if (k) bus rides are taken, the number of transfers is (k-1). If there is no possible way to reach stop (N) from stop 1, output -1.

inputFormat

The first line contains two integers (N) and (M) (where (N) is the number of bus stops and (M) is the number of bus routes).

Each of the following (M) lines describes a bus route. Each route starts with an integer (k) representing the number of stops in that route, followed by (k) integers which indicate the sequence of bus stops for that route.

outputFormat

Output a single integer representing the minimum number of transfers required (which is the number of bus rides minus one) to travel from stop 1 to stop (N). If it is impossible to reach stop (N), output -1.

sample

5 3
3 1 2 5
4 1 3 4 2
3 2 3 5

0