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

Poveste şi cerinţă...

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

h2. Date de intrare

Fişierul de intrare $prietene.in$ ...

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

Î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

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. prietene.in |_. prietene.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

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

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