Graf? Jesteś pewien?#233
Jeśli nie wierzysz, nie osiągniesz.
Początkowo istnieje wierzchołków i brak krawędzi. Każda dodana krawędź ma napisaną na niej liczbę całkowitą c_i. Definiujemy prostą ścieżkę między dwoma wierzchołkami i , należącymi do tej samej składowej, jako najkrótszą ścieżkę od do . Rozważmy prostą ścieżkę między dwoma wierzchołkami jako dobrą, jeśli każda wartość na tej ścieżce ma parzystą liczbę wystąpień. Musisz odpowiedzieć na zapytań o typach:
1 \: u \: v \: c \: (1 \le c \le 4 \cdot 10^9) — dodaj krawędź łączącą wierzchołki i z wartością na niej
2 \: u \: v \: — powiedz, czy prosta ścieżka między wierzchołkami i jest dobra. Jeśli nie ma między nimi ścieżki, wydrukuj
— powiedz, ile jest par wierzchołków i (1 \leq a < b \leq n), takich że należą do tej samej składowej z i ścieżka między nimi jest uważana za dobrą
— powiedz, ile jest par wierzchołków i (1 \leq a < b \leq n), takich że ścieżka między nimi jest uważana za dobrą, a istnieje ścieżka od do .
Zapewnione jest, że we wszystkich zapytaniach pierwszego typu krawędź łączy dwie różne składowe.
Pierwsza linia wejścia zawiera dwie liczby całkowite (1 \le n \le 2 \cdot 10^5) i (1 \le q \le 2 \cdot 10^5) — liczba wierzchołków i zapytań odpowiednio.
Każda z następujących linii zawiera opis zapytania. Pierwsza liczba całkowita t_i definiuje typ zapytania.
t_i = 1\: definiuje zapytanie pierwszego typu i jest następowane przez liczby całkowite , (1 \leq u \neq v \leq n), (1 \le c \le 4 \cdot 10^9)
t_i = 2\: definiuje zapytanie drugiego typu i jest następowane przez liczby całkowite , (1 \le u,v \le n)
t_i = 3\: definiuje zapytanie trzeciego typu i jest następowane przez liczbę całkowitą (1 \le u \le n)
t_i = 4\: definiuje zapytanie czwartego typu.
Dla każdego zapytania typu wydrukuj
-1, jeśli nie istnieje prosta ścieżka
YES, jeśli prosta ścieżka jest uważana za dobrą
NO w przeciwnym razie.
Dla każdego zapytania typów lub wydrukuj jedną liczbę całkowitą — odpowiedź na odpowiadające zapytanie.
Musisz odpowiedzieć na zapytania w kolejności, w jakiej się pojawiają w wejściu.
Przykład 1
( punktów): dla wszystkich t_i=1 u_i = 1;
( punktów): n,q \le 20;
( punktów): n,q \le 1000;
( punkty): t_i \le t_{i+1}, t_i \le 2, c = 1;
( punktów): t_i \le t_{i+1}, t_i \le 2, c \le 8;
( punktów): t_i \le t_{i+1}, t_i \le 2;
( punktów): q = n, t_i = 1 dla 1 \le i < n, t_q = 4;
( punktów): istnieje liczba całkowita taka, że wszystkie t_i = 1 dla wszystkich 1 \le i \le e, a dla wszystkich e < j \le q t_i \neq 1;
( punktów): c \le 1000, graf i testy są generowane losowo, tzn. dla każdego wierzchołka (2 \le v \le n) losowo wybieramy p_v (1 \le p_v < v), następnie generujemy losową permutację i ustawiamy v = perm_v, p_v = perm_{p_v}. Typ zapytania jest wybierany losowo (nie wybierzemy pierwszego typu, jeśli nie ma krawędzi do dodania). Wszystkie wartości w zapytaniach są wybierane losowo;
( punktów): brak dodatkowych ograniczeń.