gossips

Gossips

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

Poveste şi cerinţă...

Poli este în primul an la facultate. Chiar dacă s-a dus la una dintre cele mai bune universităţi ea şi-a dat seama repede că toţi colegii săi s-au împărţit în $N$ grupuri de prieteni, principalul scop al acestor grupuri fiind răspândirea bârfelor. Poli ştie că fiecare grup $i$ este format din unul sau mai multe subgrupuri astfel încât orice subgrup poate face parte doar dintr-un singur grup. Să presupunem că un grup $i$ află o bârfă despre un grup $j$: atunci toate subgrupurile lui $i$ (şi subgrupurile subgrupurilor acestuia, etc.) şi toate grupurile din care $i$ face parte ştiu bârfa despre grupul $j$. De asemenea, toate aceste grupuri ştiu bârfa despre fiecare grup pentru care grupul $j$ este parte a sa (dar nu ştiu nimic despre subgrupurile lui $j$, deoarece acei membri s-ar putea să nu fie implicaţi în bârfă).
Deoarece Poli este prietenă cu cu fiecare din colegii săi, ea ştie atunci când apare o bârfa (adică atunci când un grup $i$ găseşte o bârfă despre un grup $j$). Acum ea doreşte să poată răspunde rapid la întrebări de forma: “Ştie grupul $i$ o bârfă despre grupul $j$?”.
Din păcate facultatea lui Poli este cam mare, aşa că voi trebuie să o ajutaţi.

h2. Date de intrare

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

Pe prima linie a fişierului $gossips.in$ se află trei numere $N$ – numărul de grupuri, $M$ – numărul de relaţii între grupuri şi $Q$ – numărul de query-uri.
Următoarele $M$ linii sunt de forma $a b$ semnificând că grupul $b$ face parte din grupul $a$.
Următoarele $Q$ linii au fiecare trei numere: $s$ – tipul query-ului şi $x y$ – două grupuri, Dacă $s$ este $1$ atunci trebuie să răspundeţi cu “{$YES$}” dacă grupul $x$ ştie cel putin o bârfă despre grupul $y$ sau “{$NO$}” în caz contrar. Daca $s$ este $2$ atunci grupul $x$ tocmai a aflat o bârfa despre grupul $y$.

h2. Date de ieşire

În fişierul de ieşire $gossips.out$ ...

Fişierul $gossips.out$ trebuie să conţină mai multe linii, câte una pentru fiecare query de tipul $1$, fiecare linie fiind “{$YES$}” sau “{$NO$}” (fără ghilimele).
 

h2. Restricţii

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

* $1 ≤ N, Q ≤ 100.000$
* $1 ≤ M < N$
* $1 ≤ x, y ≤ N$
* dacă un grup $i$ cunoaşte o bârfă despre un grup $j$ nu înseamnă că şi $j$ cunoaşte o bârfă despre $i$

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

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

| 9 7 7
6 1
6 2
7 6
7 3
8 4
8 5
9 7
2 6 4
2 8 6
1 2 4
1 2 5
1 4 7
1 8 1
1 5 9
| YES
NO
YES
NO
YES

|

h3. Explicaţie
 
...

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

5346