P5767 [NOI1997] Optimal Bus Transfer

City H is a tourist city, and every year tens of thousands of people come to visit. To make it convenient for tourists, the bus company has set up bus stops at various attractions, hotels, restaurants, and other places, and has opened some one-way bus routes. Each one-way bus route starts from a bus stop, passes through several bus stops in order, and finally arrives at the terminal bus stop. A traveler is recently visiting City H and wants to go to Park S. However, if there is no bus that can take him directly from the stop near his hotel to Park S, he may need to take one bus for several stops, get off, and transfer to another bus at the same stop. After transferring several times, he can reach Park S. Now all bus stops in City H are numbered with integers $1, 2, \dots, N$. By convention, the bus stop near the traveler’s hotel is numbered $1$, and the bus stop for Park S is numbered $N$. Write a program to help this traveler find an optimal travel plan, so that the number of transfers during the trip from the hotel to Park S is minimized.

The first line contains two numbers $M$ and $N$ ($1 \le M \le 100$, $1 < N \le 500$), meaning there are $M$ one-way bus routes in service and a total of $N$ bus stops. Lines $2$ to $M + 1$ give the information for bus routes $1$ to $M$ in order. Line $i + 1$ gives the information for route $i$. From left to right, it lists all stop numbers on this route in the running order, and adjacent stop numbers are separated by one space.

Only one line. If it is impossible to reach Park S by bus from the hotel, output `NO`. Otherwise, output the minimum number of transfers found by your program. A transfer count of $0$ means that it can be reached without any transfer.

Translated by ChatGPT 5