entries

Time limit: 0.15s Memory limit: 32MB Input: entries.in Output: entries.out

Se consideră un graf care inițial este format din PP noduri izolate, etichetate de la 11 la PP. Se mai consideră NN intrari, unde intrare poate însemna:

  • comandă – o comandă are forma I+J, cu semnificația că în graf se adaugă muchia care unește nodurile II și JJ (dacă II și JJ erau deja unite în acel moment, nu se întreprinde nici o acțiune);
  • întrebare – o întrebare este de forma I?J, adică se întreabă dacă în acel moment II și JJ sunt în aceeasi componentă conexă.

Cerință

Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se „unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă.

Date de intrare

Din fisierul entries.in veți citi de pe prima linie numărul NN de intrări. Pe următoarele NN linii se găsesc intrările, câte una pe linie. O intrare este codificată prin trei numere separate prin câte un blanc. Primele două numere reprezintă nodurile II și JJ (numere întregi, cuprinse între 11 și PP), iar al treilea este 11 dacă intrarea este o comandă, respectiv 22 dacă intrarea este o întrebare.

Date de ieșire

La fiecare întrebare, veți scrie pe o linie separată în fișierul entries.out numărul 11 dacă nodurile despre care ați fost întrebat sunt în acel moment în aceeași componentă conexă, respectiv numărul 00 în caz contrar.

Restricții și precizări

  • Pentru 4040 de puncte: 1N5 0001 ≤ N ≤ 5 \ 000, 1P10 000 0001 ≤ P ≤ 10 \ 000 \ 000
  • Pentru alte 6060 de puncte: 1N100 0001 ≤ N ≤ 100 \ 000, 1P500 000 0001 ≤ P ≤ 500 \ 000 \ 000
  • Problema a fost modificată

Exemplu

entries.in

9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2

entries.out

0
0
1
0
1
0

Log in or sign up to be able to send submissions!