Fişierul intrare/ieşire:prietene.in, prietene.outSursăConcursul Naţional de Informatică Urmaşii lui Moisil 2017
AutorValentin RoscaAdăugată devaliro21FII Valentin Rosca valiro21
Timp execuţie pe test3 secLimită de memorie12096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Prietene

Fie un graf orientat cu N noduri şi M arce. Spunem că nodul u este super-adiacent cu v dacă există nodul t, diferit de u şi v astfel încât există arc de la u la t ( u este adiacent cu t ) şi există arc de la t la v ( t este adiacent cu v ). Numim prietene două noduri distincte x şi y pentru care mulţimea formată din adiacenţii şi super-adiacenţii lui x, diferiţi de x şi y , coincide cu mulţimea formată din adiacenţii şi super-adiacenţii lui y , diferiţi de x şi y .

Se efectuează asupra grafului dat următoarele tipuri de operaţii:

  • a x y – se adaugă un arc de la nodul x la nodul y
  • d x y – se şterge arcul de la nodul x la nodul y
  • q x y – se doreşte răspunsul la întrebarea “Nodurile x şi y sunt prietene?”

Cerinţă

Date N , numărul de noduri, M, numărul de arce, cele M arce, OP, numărul de operaţii şi lista acestora, să se efectueze
operaţiile în ordinea din listă şi să se afişeze răspunsurile la operaţiile de tip q atunci când apar.

Date de intrare

Fişierul de intrare prietene.in conţine pe prima linie T , numărul de teste din fişier, pe linia următoare numerele naturale nenule N şi M, separate printr-un spaţiu. Pe fiecare dintre următoarele M linii, se vor afla câte două valori x y, separate printr-un spaţiu, cu semnificaţia că există arc de la nodul x la nodul y . Pe linia linia următoare se află OP , numărul de operaţii care trebuie efectuate peste graful din testul curent. Pe fiecare dintre următoarele OP linii se află câte o operaţie, având forma precizată în enunţ. Următoarele teste din fişier au acelaşi format.

Date de ieşire

În fişierul de ieşire prietene.out se va afişa pe câte o linie, răspunsul la operaţiile de tip q , în ordinea în care acestea apar în fişierul de intrare. Răspunsul este YES dacă nodurile din operaţia q sunt prietene şi NO , în caz contrar.

Restricţii

  • 1 ≤ N ≤ 150
  • 1 ≤ M ≤ 22500
  • 1 ≤ OP ≤ 730.000
  • Numărul de operaţii a şi d nu va depăşi 22500 pe test
  • Fişierul de intrare nu conţine operaţii a care să adauge arce existente şi nici d care să şteargă arce care nu apar în graf
    la acel moment.
  • Într-un fişier de test pot fi maxim 3 grafuri cu operaţiile corespunzătoare, descrise ca în datele de intrare.

Exemplu

prietene.inprietene.out
1
4 5
1 2
2 1
3 4
3 2
1 4
9
q 1 4
a 4 3
d 3 2
q 1 4
d 1 4
q 2 1
a 4 2
a 1 3
q 1 3
NO
NO
YES
YES

Explicaţie

La prima operaţie q 1 4 mulţimea corespunzătoare nodului 4 este mulţimea vidă iar cea corespunzătoare lui 1 este {2,4,1} - {1,4} = {2}, deci răspunsul este NO. Adăugăm arcul (4,3) şi eliminăm arcul (3,2). La următoarea operaţie q 1 4 mulţimea corespunzătoare lui 1 este {2,4,1,3} - {1,4} = {2,3} iar cea corespunzătoare lui 4 este {3,4} - {1,4} = {3}, deci răspunsul este NO. Ştergem arcul (1,4) apoi, la următoarea operaţie q 2 1 mulţimea lui 2 este {1,2} - {1,2} = ∅ iar cea corespunzătoare lui 1 este tot {1,2} - {1,2} = ∅, deci răspunsul este YES, deoarece ambele mulţimi sunt vide.
Adăugăm arcele (4,2) şi (1,3) apoi la ultima operaţie q 1 3 mulţimea lui 1 este {1,2,3,4} - {1,3} = {2,4} iar cea corespunzătoare lui 3 este {2,3,4} - {1,3} = {2,4}, deci răspunsul este YES.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?