NOI '97 P2 - Optimal Routing

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 16M

Problem type
National Olympiad in Informatics, China, 1997

City H is a popular tourist attraction with thousands of visitors every year. For the convenience of tourists, a bus company has established N bus stops (labeled from 1 to N) and M one-way routes around locations like hotels and restaurants. Each one-way route starts at some initial bus stop, passes through some number of other stops, and terminates at a final bus stop.

A tourist has arrived at city H, and is currently at a restaurant near bus stop 1. He really wants to visit park S near bus stop N. However if from his current location there is no single bus route that can take him to the park, he might have to take a bus for one or more stops, get off, transfer to another bus passing through the stop at which he got off, and repeat several times until he finally reaches his destination.

Write a program to help this tourist find an optimal bus route from the restaurant to the park, such that the number of transfers during his route is as small as possible.

Input Specification

The first line of input contains two integers M and N (1 \le M \le
100, 1 < N \le 500), indicating the number of one-way bus routes and the number of bus stops that the company built. The (i+1)-th line of input describes the i-th bus route (for 1 \le i \le M). Each of these lines will have some number of space-separated integers from 1 to N, indicating the stops numbers that the route passes through in the order that they are given.

Output Specification

The output should contain one line - the minimum number of transfers that the tourist is required to make to get to park S, or a single line with the string NO if it is not possible to reach the park from the restaurant. Note that if the number of transfers is 0, the tourist can directly reach the park without making any transfers.

Sample Input

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

Sample Output


Problem translated to English by Alex.


There are no comments at the moment.