Fişierul intrare/ieşire:santa.in, santa.outSursăStelele Informaticii 2005, clasele 11-12
AutorSorin Stancu-MaraAdăugată de
Timp execuţie pe test2.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Santa

HO HO HO... Max Damage a ajuns in Laponia, mai precis la fabrica de tractorase a lui Mos Craciun. Acum, toata lumea stie ca Mos Craciun are o lista cu copiii care au fost cuminti si ca le aduce in noaptea de ajun cate o jucarie, dar... sa zicem ca Max Damage nu mai e copil. El stie ca jucariile sunt gata si ca spiridusii vor trebui sa le duca de la atelierul lor (aflat in intersectia notata cu S) la casuta Mosului (aflata in intersectia notata cu E). Max Damage are o harta a orasului. Pe ea apar N intersectii, numerotate de la 1 la N , unite de M strazi. Acum Max Damage isi face urmatorul plan si are nevoie de ajutorul nostru. Stie ca maine spiridusii vor transporta jucariile de la atelier la casuta lui Mos Craciun. Problema este ca nu stie exact pe ce drum vor merge spiridusii, insa este cert ca ei nu vor trece de doua ori printr-o intersectie. Tot ce mai ramane de facut este ca Max sa sara in masina si sa verifice toate intersectiile in care s-ar putea gasi transportul de jucarii. Fiind si econom el nu trebuie sa treaca printr-o intersectie de doua ori sau prin intersectiile in care se stie sigur ca transportul de jucarii nu poate ajunge (sa fim seriosi, benzina costa destul de mult). Astfel el va pleca din "sediul" sau (intersectia notata cu Q) trecand prin toate si numai prin intersectiile unde transportul de jucarii ar putea ajunge. Turul de verificare facut de Max poate sa se sfarseasca in orice intersectie.

Cerinta

Daca este posibila realizarea unui astfel de drum Max Damage va cere unul dintre ele.

Date de Intrare

Prima linie a fisierului de intrare santa.in contine doua numere intregi N , M reprezentand numarul de intersectii, respectiv de strazi. Urmatoarele M linii contin cate doua numere Xi , Yi reprezentand faptul ca exista o strada, care poate fi parcursa in ambele directii, intre intersectiile Xi si Yi. Pe ultima linie se afla trei numere S , E , Q cu semnificatia de mai sus.

Date de Iesire

In fisierul santa.out veti afisa No chance daca Max nu isi poate realiza planul pentru fisierul de intrare corespunzator, sau numarul X de intersectii (aflat pe prima linie) ce trebuie vizitate pentru a-si realiza planul, iar pe linia urmatoare numerele A1 A2 ... Ax separate prin spatii reprezentand intersectiile, in ordinea in care Max Damage treace pentru verificare.

Restrictii si precizari

  • 1 ≤ N ≤ 45.000
  • 1 ≤ M ≤ 130.000
  • oricum am alege un set de 16 sau mai multe intersectii exista doua intersectii in set A si B astfel incat este imposibil sa gasim un drum care pleaca din A , trece prin B si revine in A trecand printr-o intersectie cel mult odata(drumul poate sa treaca prin orice intersectie nu neaparat prin cele din setul ales).

Exemplu

santa.insanta.out
5 5
1 2
1 4
2 3
3 4
4 5
1 4 2
4
2 1 4 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content