변의 수

새로운 메타.

무방향 그래프의 지그재그 사이클은 꼭짓점의 수열 $a_0, a_1, \ldots, a_{k-1}$로서, 꼭짓점이 서로 다를 필요는 없으며, 모든 $i: 0 \leq i < k$에 대해 $a_i$와 $a_{(i+1) \mod k}$가 그래프에서 인접하고 다음 중 하나가 성립하는 수열이다.

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}$

사이클이 변 $(u, v)$를 $p$번 포함한다는 것은 $a_i = u, a_{(i+1) \mod k} = v$ 또는 $a_i = v, a_{(i+1) \mod k} = u$인 서로 다른 $i: 0 \leq i < k$가 정확히 $p$개 존재한다는 뜻이다.

그래프가 분할 가능하다는 것은 지그재그 사이클의 집합이 존재하여, 각 변에 대해 정확히 하나의 사이클이 그 변을 $1$번 포함하고 나머지 모든 사이클은 그 변을 $0$번 포함한다는 뜻이다. 즉 그래프의 변을 지그재그 사이클로 분할할 수 있다는 뜻이다.

처음에 비어 있는 그래프가 있다. 다음 두 종류의 질의를 처리하자.

1. 꼭짓점 $u$와 $v$ 사이에 변을 추가한다.
2. 꼭짓점 $u$와 $v$ 사이의 변을 제거한다.

각 질의 후에 그래프가 분할 가능한지 출력한다.

첫째 줄에 두 정수 $n$과 $q$가 주어진다. ($2 \leq n \leq 3 \cdot 10^5, 1 \leq q \leq 3 \cdot 10^5$) $n$은 그래프의 꼭짓점 수, $q$는 질의의 수이다.

다음 $q$개의 줄이 주어진다. 그중 $i$번째 줄에는 세 정수 $t, u, v$가 주어진다. ($t \in \{1, 2\}, 1 \leq u < v \leq n$) $t$는 질의의 종류이고, $u$와 $v$는 $t = 1$이면 추가할 변, $t = 2$이면 제거할 변의 양 끝점이다. 이미 있는 변을 추가하거나 없는 변을 제거하라는 질의는 주어지지 않는다.

$q$개의 줄을 출력한다. $i$번째 줄에는 처음 $i$개의 질의를 처리한 후 그래프가 분할 가능하면 1, 아니면 0을 출력한다.

모든 질의를 처리한 후 가능한 지그재그 사이클 집합 중 하나는 $\{[1,4,3,5], [2,6,4,5]\}$이다.