== include(page="template/taskheader" task_id="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.

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?”

* *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?”
 
h2. Cerintă
 
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.

h2. 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.

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.

h2. Date de ieşire

h3. 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,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,4}={2} iar cea corespunzătoare lui 4 este {3}-{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 tot {1,2,3,4}–{1,3}={2,4}, deci răspunsul este YES.
 

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 tot {1,2,3,4} - {1,3} = {2,4}, deci răspunsul este YES.

== include(page="template/taskfooter" task_id="prietene") ==