$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Аутобуске руте

vreme memorija ulaz izlaz
0,5 s 64 Mb standardni izlaz standardni ulaz

Познате су руте аутобуса у једном граду. Напиши програм који одређује најмањи број вожњи аутобусом потребан да се стигне од дате почетне до дате завршне станице.

Улаз

Са стандардног улаза се уноси број аутобуса \(n\) (\(1 \leq n \leq 10^5\)). Наредних \(n\) редова описује руте тих \(n\) аутобуса. За сваку руту је наведен број \(m\) (\(1 \leq m \leq 10^5\)) станица дуж те руте, а затим и \(m\) различитих редних бројева који представљају станице дуж руте. Аутобуси дуж руте пролазе у оба смера. Укупан број различитих станица на свим рутама није већи од \(10^5\), а укупан збир бројева свих станица на свим рутама није већи од \(5\cdot 10^6\). У последњем реду се налазе редни бројеви две станице – почетне и крајње.

Излаз

На стандардни излаз исписати минимални број вожњи потребан да се стигне са почетне до крајње станице. Ако није могуће стићи, исписати -1.

Пример

Улаз

2 3 1 2 7 3 3 6 7 1 6

Излаз

2

Објашњење

Најбоље је на станици 1 се укрцати на први аутобус, ићи до станице 7 и тамо прећи на други аутобус који ће нас одвести до станице 6.

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.