멋진 연결 요소와 쿼리

연결 요소의 모든 간선이 서로 다른 색의 정점을 연결하고 있을 때 그 연결 요소를 멋진 연결 요소라고 한다.

그래프 $G$는 각 정점의 색이 빨간색 또는 파란색이고 간선이 없는 그래프이다. $G$에 다음 쿼리를 수행하는 프로그램을 작성해 보자.

$1$ $u$ $v$: 서로 다른 두 정점 $u$와 $v$를 잇는 간선을 추가한다. 가능하다면 해당 간선을 포함하는 연결 요소에 존재하는 정점의 색깔을 $0$개 이상 변경하여 멋진 연결 요소로 만든다. 가능한 방법이 여러 가지 존재한다면 그중 가장 적은 횟수로 변경하는 방법으로 변경한다.
$2$ $u$: 정점 $u$를 포함하는 연결 요소의 모든 정점의 색깔을 변경한다.
$3$ $c$: 현재 $G$에 존재하는 멋진 연결 요소 중 $c$가 $0$인 경우 빨간색, $c$가 $1$인 경우 파란색 정점이 가장 많은 연결 요소를 선택한다. 선택한 멋진 연결 요소에 포함된 정점들의 번호 중 가장 작은 것을 출력한다.

쿼리가 누적해서 수행됨에 유의하여라.

첫째 줄에 정점의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 10^5;$ $1 \le Q \le 10^5)$

둘째 줄에 $1$, $2$, $\cdots$, $N$번 정점의 색을 나타내는 정수 $c_1$, $c_2$, $\cdots$, $c_N$이 공백으로 구분되어 주어진다. $0$은 빨간색, $1$은 파란색 정점을 의미한다.

셋째 줄부터 $Q$개 줄에 걸쳐 쿼리가 주어진다.

$1$번 쿼리에서 고른 두 정점 $u$와 $v$ 사이에는 간선이 없다. $1$번 쿼리를 수행하는 방법이 유일한 입력만 주어진다.

$3$번 쿼리는 하나 이상 주어진다. $3$번 쿼리는 멋진 연결 요소가 있을 때만 주어지며 쿼리의 답이 유일한 경우만 주어진다.

$3$번 쿼리가 주어질 때마다 쿼리의 답을 한 줄에 하나씩 출력한다.

연결 요소는 간선을 통해 연결된 부분그래프이다. 엄밀하게 아래 조건을 만족하는 경우를 연결 요소라고 한다.