Description

ChaoChao’s home is far away from school, so he should take bus every day.
Now we know all bus start from a station, through some stations and finally arrive at a station. All ways are unidirectional. But to his annoyance, it’s hard to find a nonstop bus from his home to the school (maybe he would not find). He usually has to take one bus to a station and take another bus at this station to next station and so on. He arrives at school ultimately.
Fortunately, there is a station in front of his home and also another station in front of school. ChaoChao doesn’t like waiting for bus, so he decides to choose a way which spends the least times transferring.
Assuming that bus station's number is $1,2,... ,N$. The number of the bus station which in front of his home is 1, in front of school is $N$.
Your task: help ChaoChao to find a best way to spend the least times transferring.

Format

Input

The first line $M(M \leq 100)$, represents $M$ ways. The second line $N(N \leq 500)$, represents $N$ bus stations.

Then followed M lines, the $i-th$ line gives the bus station number from left to right separated by spaces.

Output

If ChaoChao can’t go to school from home by bus, output “-1”.
Otherwise, output the least times changing bus.
If ChaoChao can arrive at school and didn’t change bus, output 0.

Samples

3
7
6 7
4 7 3 6
1 2 3 5

2