Els trens de Porto P70880

Statement

thehtml

Com a cada SWERC, el professor Oak perpetua una tradició que assegura que algun equip UPC guanyi: menjar un cop a un Burguer King. Hi han quedat tots a una hora convenida, però el professor hi ha anat directament, mentre que els tres equips s’han quedat a l’hotel jug... d’això, “entrenant fort” fins a l’hora de sortir. Quan, finalment, els equips han agafat els Ferrocarrils de Màxima Estupidesa (FME) de Porto, en algun moment s’han equivocat de camí. Alguns dels concursants es conformen culpant al Rafa fent jocs de paraules (“Dijikstre que el tren era este!”), però altres intenten arribar a temps en qualsevol cas.

Podeu ajudar els equips UPC? Sembla que ells no saben calcular camins mínims! Donats els horaris dels trens de la FME, i la posició dels equips UPC en aquest moment, heu de calcular el temps mínim necessari per arribar al Burger King.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre d’estacions n i el nombre de línies de tren m, seguits de la informació de cada línia: el nombre d’estacions k_i, seguit de les k_i estacions en ordre. Finalment, tenim l’estació u on estan els equips UPC i l’estació b on es troba el Burger King.

Podeu suposar 2 ≤ n ≤ 10⁴, 1 ≤ m_i ≤ 1000, 2 ≤ k_i ≤ 100, i u ≠ b. Les estacions es numeren entre 1 i n. Les línies de tren no tenen estacions repetides, van en els dos sentits, i no són circulars. A cada minut, surt un tren de cada estació en els dos sentits. Els trens triguen un minut en anar des d’una estació a la següent. Suposeu que els transbordaments entre línies són instantanis. Sempre hi ha algun camí entre u i b.

Sortida

Per a cada cas, escriviu el temps mínim per anar de u a b.

Public test cases

Input

6 1
6  1 6 5 2 3 4
4 1

11 4
2  10 4
7  2 6 7 8 9 10 4
8  11 1 2 3 4 6 8 10
5  9 3 4 7 10
1 10

Output

5
4

Information

Author: Ángel García
Language: Catalan
Official solutions: C++
User solutions: C++