Fişierul intrare/ieşire: | incurcatura.in, incurcatura.out | Sursă | ONI 2017, clasele 11-12 |
Autor | Eugenie Daniel Posdarascu, Lucian Bicsi, Razvan Salajan | Adăugată de | Matteo Verzotti •Matteoalexandru |
Timp execuţie pe test | 0.6 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Incurcatura
Cu ocazia Olimpiadei Naţionale de Informatică, Ninel (fratele mai mic al lui Gigel), a primit un graf neorientat conex G cu N noduri, numerotate de la 1 la N. Acesta a scris pe o foaie lista de vecini corespunzătoare fiecărui nod. Poznaş din fire, Gigel a schimbat lista de vecini pentru unul sau două noduri, schimbând astfel nodurile adiacente acestora. Mai exact, dacă un nod are X vecini, Gigel va scrie tot X vecini, dintre care unii nu vor coincide cu cei scrişi iniţial de Ninel.
Cerinţă
Cunoscând atât numărul de modificări făcute de Gigel, cât şi listele de adiacenţă corespunzătoare fiecărui nod după modificările făcute de Gigel, se cere să se afle nodul sau cele 2 noduri cărora Gigel le-a schimbat listele de adiacenţă.
Date de intrare
Fişierul incurcatura.in conţine pe prima linie un singur număr natural P, reprezentând numărul de noduri care au suferit modificări. Pe a doua linie se va afla un singur număr natural N, reprezentând numărul de noduri ale grafului, iar pe fiecare dintre următoarele N linii, separate printr-un spaţiu se află:
- un număr natural , reprezentând numărul de vecini ai nodului i, atât înainte cât şi după efectuarea operaţiilor;
- numere naturale distincte din mulţimea , reprezentând vecinii nodului i, după efectuarea operaţiilor.
Date de ieşire
Dacă P = 1 fişierul incurcatura.out va conţine pe prima linie nodul care a fost modificat.
Dacă P = 2 fişierul incurcatura.out va conţine pe prima linie nodurile care au fost modificate, în ordine crescătoare, separate printr-un spaţiu.
Restricţii
- pentru datele de intrare problema întotdeauna are soluţie
- se garantează că pentru datele de intrare, soluţia este unică
- , pentru orice i de la 1 la N
- Pentru 40% din teste P = 1
Exemplu
incurcatura.in | incurcatura.out | Explicaţie |
---|---|---|
2 7 4 7 3 2 4 2 6 1 4 7 6 4 1 4 1 3 5 6 2 4 1 3 7 5 1 1 3 | 1 6 | Gigel a modificat listele de adiacenţă corespunzătoare nodurilor 1 şi 6. |