Fişierul intrare/ieşire:	prietene.in, prietene.out	Sursă	Concursul Naţional de Informatică Urmaşii lui Moisil 2017
Autor	Valentin Rosca	Adăugată de	Valentin Rosca •valiro21
Timp execuţie pe test	1.5 sec	Limită de memorie	12096 kbytes
Scorul tău	N/A	Dificultate	N/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?”

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

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.

Cum se trimit solutii?