== 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:

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.

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

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

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

h2. Restricţii

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

* Într-un fişier de test pot fi maxim $3$ grafuri cu operaţiile corespunzătoare, descrise ca în datele de intrare.

h2. Exemplu