Tired of the cold winter weather, Bessie the cow plans to fly to a warmer destination for vacation. Only one airline, Air Bovinia, is willing to sell tickets to cows.

Air Bovinia owns N planes (1 <= N <= 500), each of which flies on a specific "route" consisting of two or more cities. No city appears multiple times in a route. If Bessie uses a route, she can board at any city along the route and disembark at any city later along the route. Each route has a certain cost, which Bessie must pay if she uses any part of the route, irrespective of the number of cities she visits.

Bessie would like to find the cheapest way to travel from her farm (city A) to her destination (city B). Since she does not want a complicated itinerary, she wants to use only a single route. Please help her decide the minimum cost she must pay.

Line 1: A, B, and N, separated by spaces.

The next 2N lines describe the available routes, two lines per route. The first line contains the cost of the route (1..1000) and the number of cities along the route (1..500). The second line lists the cities in order along the route. Each city is an integer in the range 1..10,000.

The minimum cost of a single route Bessie can use to travel from city A to city B. If there is no such route, output -1.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > January > Bronze