23686번 - Number Of Vertices 다국어

New meta.

A zigzag cycle in an undirected graph is a sequence of vertices $a_0, a_1, \ldots, a_{k-1}$, \uline{not necessarily distinct}, such that for all $i: 0 \leq i < k$ $a_i$ and $a_{(i+1) \mod k}$ are adjacent in the graph and one of the following holds:

1. $a_{(i+k-1)\mod k} < a_i, a_i > a_{(i+1) \mod k}$
2. $a_{(i+k-1)\mod k} > a_i, a_i < a_{(i+1) \mod k}$

A cycle contains the edge $(u, v)$ $p$ times if there exist exactly $p$ distinct $i: 0 \leq i < k$, such that $a_i = u, a_{(i+1) \mod k} = v$ or $a_i = v, a_{(i+1) \mod k} = u$. 

A graph is splittable if there exists a set of zigzag cycles, such that for each edge exactly one cycle contains it $1$ time and all the remaining cycles contain it $0$ times, i.e. you can split edges of the graph into zigzag cycles.

There is a graph which is initially empty. Process the following types of queries:

1. Add an edge between vertices $u$ and $v$.
2. Remove an edge between vertices $u$ and $v$.

After each query print whether the graph is splittable.

The first line contains two integers $n$ and $q$ ($2 \leq n \leq 3 \cdot 10^5, 1 \leq q \leq 3 \cdot 10^5$) --- the number of vertices in the graph and the number of queries, respectively.

$q$ lines follow. $i$-th of them contains three integers $t, u, v$ ($t \in \{1, 2\}, 1 \leq u < v \leq n$) --- the type of query and the endpoints of the edge you have to add if $t = 1$ or remove if $t = 2$. No query will ask to you to add an already present edge or to delete an absent one.

Print $q$ lines. $i$-th of them should contain 1 if the graph is splittable after the first $i$ queries and 0 otherwise.

After processing all the queries one possible set of zigzag cycles is $\{[1,4,3,5], [2,6,4,5]\}$.