| Fişierul intrare/ieşire: | autobuze2.in, autobuze2.out | Sursă | Infoarena Monthly 2014, Runda 5 |
| Autor | Andrei Cristian Lambru | Adăugată de |  Cristian Lambru •maritim |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Autobuze2
După tot acest timp petrecut alături de Antonia în vacanţă, Antonio a început să o îndrăgească din ce în ce mai mult pe colega sa de la litere. Cum Antonia este nouă în Bucureşti, acesta s-a gândit să îi facă un tur inedit al oraşului, plimbând-o cu autobuzele. El crede că în acest fel, îi va putea câştiga şi atenţia fetei.
Harta oraşului este reprezentată prin N intersecţii, conectate între ele prin M străzi bidirecţionale. În fiecare intersecţie este amplasată o staţie de autobuz. În total sunt B autobuze. Pentru fiecare autobuz i (1 ≤ i ≤ B) se cunoaşte traseul acestuia, sub forma a Ki staţii: A 1, A 2, ..., A Ki. Autobuzul parcurge aceste staţii în ordine, urmând ca din staţia A Ki să plece din nou spre staţia A 1, de unde va repeta acelaşi traseu. Altfel spus, autobuzele îşi parcurg traseul ciclic.
Cerinţă
Antonio vrea să plece cu Antonia din staţia 1 şi să ajungă în staţia N, mergând doar cu autobuzele. Pentru că nu vrea ca Antonia să se plictisească prea tare, acesta se întreabă care este numărul minim de staţii pe care trebuie să le parcurgă. În cazul în care cei doi nu pot ajunge din staţia 1 în staţia N mergând doar cu autobuzele, Antonio îşi va lua inima în dinţi şi o va scoate pe Antonia la un suc.
Date de intrare
Fişierul de intrare autobuze2.in conţine pe prima linie două numere naturale N şi M, având semnificaţia din enunţ. Pe fiecare din următoarele M linii se găsesc câte două numere naturale x şi y, reprezentând faptul că există o stradă bidirecţională care conectează intersecţia x de intersecţia y. Pe următoarea linie se află numărul B. Fiecare linie i din următoarele B conţine numărul natural Ki, urmat de Ki numere naturale A 1, A 2, ..., A Ki, separate între ele printr-un spaţiu.
Date de ieşire
În fişierul de ieşire autobuze2.out se va găsi un singur număr natural, reprezentând numărul minim de staţii prin care vor trece Antonio şi Antonia. În cazul în care cei doi nu pot ajunge din staţia 1 în staţia N mergând doar cu autobuzele, se va afişa "Iesim la un suc?", fără ghilimele.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 200.000
- 1 ≤ B ≤ 100
- 2 ≤ Ki ≤ 100, 1 ≤ i ≤ B
- Se garantează că între oricare două staţii consecutive din traseul unui autobuz există o stradă directă.
- Se garantează că între A Ki şi A 1 există o stradă directă, pentru orice i, 1 ≤ i ≤ B.
Exemplu
| autobuze2.in | autobuze2.out | Explicatie |
|---|---|---|
| 5 6 1 5 1 2 3 1 4 5 2 4 2 5 2 4 1 2 4 5 2 2 5 | 3 | Cei doi se vor urca din staţia 1 în primul autobuz, vor coborî la staţia 2 şi vor lua al doilea autobuz. Vor coborî la staţia 5. În total, cei doi au parcurs 3 staţii de autobuz. |
| 4 5 1 2 2 3 3 4 2 4 1 4 3 2 1 2 2 2 3 2 3 2 | Iesim la un suc? | Niciun autobuz nu opreşte în staţia 4, deci Antonio îşi ia inima în dinţi. |
