Fişierul intrare/ieşire:kcity.in, kcity.outSursăAutumn Warmup 2007, Runda 3
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1.125 secLimită de memorie8096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Kcity

In orasul KCity exista N intersectii, numerotate de la 1 la N, interconectate prin M strazi bidirectionale (fiecare strada leaga 2 intersectii diferite). In ultimele luni, criminalitatea a crescut foarte mult in oras, astfel ca seful politiei doreste sa determine niste trasee pe care sa patruleze masinile politiei, pentru a mentine siguranta cetatenilor. Dupa parerea sefului politiei, fiecare traseu ar trebui sa fie de forma x1,x2,..,xP (P ≥ 1), unde xi sunt numerele unor intersectii si intre oricare doua intersectii consecutive de pe traseu, xi si xi+1, exista o strada. Pentru a evita redundantele (care, in opinia sefului politiei, ar creste prea mult costurile), un traseu nu trebuie sa contina o intersectie de mai multe ori. In plus, fiecare intersectie trebuie sa apara in exact un singur traseu (daca ar exista o intersectie care sa nu apartina nici unui traseu, ar creste foarte mult rata criminalitatii in zona respectiva).

Ajutorul sefului politiei, insa, are o parere diferita. El crede ca fiecare traseu ar trebui sa fie de forma x1, x2,..,xP (P ≥ 4), unde xi sunt numerele unor intersectii, x1=xP si intre oricare doua intersectii consecutive de pe traseu, xi si xi+1, exista o strada. Insa este si el de acord ca fiecare intersectie trebuie sa apartina exact unui singur traseu, iar un traseu nu trebuie sa contina o intersectie de mai multe ori (cu exceptia primei intersectii de pe traseu, care va fi si ultima).

Deoarece departamentul de politie nu are la dispozitie prea multi oameni, se doreste determinarea numarului minim de trasee pe care trebuie trimise patrule de politie, in fiecare din cazuri (conform definitiei a ceea ce inseamna un traseu a sefului politiei si conform definitiei ajutorului sefului). Se mai stie si ca numele orasului (KCity) nu a fost ales intamplator, el provenind de la conditia cunoscuta doar de oficialitati, ca daca intre intersectiile A si B exista o strada, atunci |A-B| ≤ K.

Date de intrare

Prima linie a fisierului de intrare kcity.in contine 4 numere intregi, separate printr-un spatiu: N, K, X si M. Fiecare din urmatoarele M linii contine cate 2 numere intregi, separate printr-un spatiu, A si B, avand semnificatia ca exista o strada intre intersectia A si intersectia B. Daca X=1, atunci se cere determinarea numarului minim de trasee care corespund cu parerea sefului politiei; daca X=2, se cere determinarea numarului minim de trasee ce corespund cu parerea ajutorului sefului.

Date de iesire

In fisierul de iesire kcity.out veti afisa numarul intreg T, reprezentand numarul minim de trasee care respecta parerea sefului politiei (daca X=1), respectiv numarul minim de trasee care respecta parerea ajutorului sefului (daca X=2). Daca nu se pot stabili trasee astfel incat sa fie respectate conditiile precizate in enunt, afisati -1.

Restrictii

  • 1 ≤ N ≤ 1000
  • 1 ≤ K ≤ 6
  • 0 ≤ M ≤ 6000
  • Nu vor exista mai multe strazi intre aceeasi pereche de intersectii.
  • In 50% din teste, X=1 (evident, in restul de 50% din teste, X=2).

Exemple

kcity.inkcity.out
9 3 1 10
1 4
2 4
1 2
3 6
6 9
9 7
7 8
8 5
5 3
4 7
1
9 3 2 10
1 4
2 4
1 2
3 6
6 9
9 7
7 8
8 5
5 3
4 7
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content