Fişierul intrare/ieşire:incurcatura.in, incurcatura.outSursăONI 2017, clasele 11-12
AutorEugenie Daniel Posdarascu, Lucian Bicsi, Razvan SalajanAdăugată deMatteoalexandruMatteo Verzotti Matteoalexandru
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 K_i, reprezentând numărul de vecini ai nodului i, atât înainte cât şi după efectuarea operaţiilor;
  • K_i numere naturale distincte din mulţimea \{1,2,...,n\} \setminus \{i\}, 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ă
  • 3 \leq N \leq 10^5^
  • 1 \leq K_i \leq N - 1, pentru orice i de la 1 la N
  • K_1 + K_2 +... + K_n \leq 4 * 10^5
  • P \in \{1, 2\}
  • Pentru 40% din teste P = 1

Exemplu

incurcatura.inincurcatura.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?