Imperiul bizantin este atacat
din nou de catre turci. Pentru a cere ajutor, solii imparatului bizantin trebuie
sa ajunga la capitalele a N regate
vecine. Intre aceste orase exista M
drumuri bidirectionale, construite in astfel incat pornind din orice oras sa
se poata ajunge in oricare alt oras, direct sau indirect, trecand prin alte
orase. Drumurile sunt insa nesigure, deoarece exista K
ghilde de hoti care le controleaza. Fiecare drum este controlat de o singura
ghilda, si pentru a fi parcurs trebuie platita o taxa de trecere (care este
aceeasi pentru toate drumurile). O ghilda de hoti poate controla mai multe drumuri,
insa nu permite trecerea decat pe cel mult unul dintre ele. De asemenea, solii
nu vor sa plateasca taxa de trecere pentru mai multe drumuri decat este necesar.
Pe un drum pentru care a fost platita taxa de trecere se poate trece de oricate
ori in orice directie.
Solii pornesc intotdeauna din orasul 1.
Cerinta
Scrieti un program care
calculeaza un numar minim de drumuri pentru care trebuie platita taxa de trecere,
astfel incat orice oras sa fie accesibil din orasul 1
mergand numai pe aceste drumuri, si nici o ghilda sa nu controleze mai mult
de un drum dintre cele alese.
Date de intrare
Fisierul de intrare sol.in
are urmatoarea structura:
- pe prima linie se afla trei numere naturale separate printr-un singur spatiu
N M K, reprezentand numarul de
orase, numarul de drumuri si numarul de ghilde in care se impart hotii;
- pe liniile 2, . . . , M+1
sunt scrise doua numere intregi separate printr-un spatiu x
y (1<=x,y<=N), cu
semnificatia ca intre orasul x
si orasul y exista drum;
- pe liniile M+2, . . . , M+K+1
este scris un intreg pi
(0<pi<=M), urmat
de pi intregi x1,
x2, …, xpi(0<xj<=M,
0<j<=pi), reprezentand numarul de drumuri controlate
de ghilda i, respectiv drumurile
care sunt controlate de aceasta. Toate numerele sunt separate printr-un singur
spatiu. Descrierea ghildei i
se afla pe linia M+i+1. Drumurile
se considera numerotate de la 1
la M in ordinea in care se gasesc
in fisierul de intrare. Fiecare drum apare exact o data pe una din liniile M+2,
. . . , M+K+1.
Date de iesire
Pe prima linie a fisierului
de iesire sol.out trebuie sa
se afle un numar intreg D, reprezentand
numarul de drumuri selectate, sau -1
daca nu exista solutie. In cazul in care exista solutie, pe urmatoarea linie
trebuie sa se afle D intregi
separati printr-un singur spatiu reprezentand drumurile selectate. Drumurile
se considera numerotate de la 1
la M in ordinea in care se gasesc
in fisierul de intrare. Ordinea in care sunt afisate drumurile nu are importanta.
Daca exista mai multe solutii, atunci oricare se considera corecta.