Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | pang.in, pang.out | Sursă | FMI No Stress 2017 |
Autor | Baltatu Andrei | Adăugată de | |
Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pang Bang
De ce am numit-o aşa?
Cu toţii ne dorim să trăim veşnic. Din păcate însă, acest lucru este improbabil. Cu toate acestea, prietenul nostru Faust, filosof şi mare înţelept, are ocazia unică de a aplica pentru firma Ludai România unde totul este posibil. Desigur, însă, înainte de asta, va trebui să treacă prin nenumărate interviuri istovitoare (ţinute, cum bine aţi intuit, de către cunoscutul Mefisto).
Faust a fost anunţat că va trebui să ia parte în următoarele zile la T probe existenţiale (de interviu). Din fericire pentru acesta, s-a produs o breşă în sistemul de poştă electronică (vinovatul nu a fost găsit), în aşa fel încât Faust, într-un mod foarte convenabil, a obţinut dinainte probele pentru toate cele T zile. În mod foarte curios, toate zilele conţineau probe foarte asemănătoare. Faust a observat că enunţul problemei era comună în fiecare dintre zile:
Eşti într-un tărâm necunoscut, care are N oraşe. Unele oraşe sunt sărace, altele sunt bogate, însă K dintre ele conţin relicve valoroase. Ce va trebui să faci este să "restitui" toate relicvele, în numele Ludai România. Poţi să proneşti din orice oraş doreşti şi poţi să te opreşti în orice oraş doreşti, însă o dată ce vei intra într-un oraş, fii sigur că nu vei mai putea ajunge vreodată înapoi (în viaţă). Alege-ţi calea în mod înţelept!
Alături de fiecare dintre cele T enunţuri pe care Mefisto se pare că nu s-a obosit să le facă să pară câtuşi de puţin diferite, se află ataşată câte o descriere a tărâmului, relicvelor şi drumurilor accesibile între oraşe, într-un format identic cu cel din fişierul pang.in. Pentru simplitate, relicvele sunt identificate de oraşul în care se află.
Cum Faust nu e tocmai un neiniţiat la şiretlicurile lui Mefisto, acesta observă că, în unele dintre teste, călătoria este una imposibilă! Cu toate acestea, datele sunt atât de imense, încât este foarte rapid copleşit de dificultatea probei. Ajută-l pe Faust să treacă toate probele de interviu, scriind câte o "foaie ajutătoare" pentru acesta! Mai exact, pentru fiecare dintre cele T probe, lui Faust i-ar plăcea să ştie dacă cerinţa din ziua respectivă este una posibilă şi, în caz afirmativ, să ştie în ce ordine să pornească în căutarea relicvelor. Astfel va putea, în sfârşit, să îşi retinerească tinereţea (căci meseria de filosof nu i-a adus prea multe beneficii până acum).
Date de intrare
Fişierul de intrare pang.in va conţine pe prima linie un număr T reprezentând numărul de teste la care trebuie să răspunzi. După vor urma T teste astfel: Pe prima linie se vor afla N, M şi K reprezentând numărul de noduri din graf, numărul de muchii din graf şi numărul de indici din şir. Pe următoarele M linii se afla 2 numere A şi B reprezentând faptul că există o muchie orientată de la A spre B. Pe ultima linie se va afla un şir de K numere, reprezentând indicii nodurilor din graf.
Date de ieşire
Fişierul de ieşire pang.out va conţine, pentru fiecare dintre cele T teste:
- " Nu " ( fară ghilimele ), în caz că nu există nicio permutare cu proprietatea din enunţ, pe o singură linie
- " Da " ( fară ghilimele ), în caz contrar, pe prima linie. Pe cea de-a doua linie se va afla şirul permutat
Restricţii
- 1 ≤ K ≤ N ≤ 105
- 1 ≤ M ≤ 2*105
- Nodurile sunt numerotate de la 1 la N
- Suma tuturor N-urilor din input ≤ 105
- Suma tuturor M-urilor din input ≤ 2*105
Exemplu
pang.in | pang.out |
---|---|
2 4 4 3 1 2 1 3 2 3 3 4 2 4 1 3 2 3 1 2 1 3 3 1 2 | Da 1 2 4 Nu |