31942번 - 멋진 연결 요소와 쿼리

문제

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

그래프 $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ドル$번 쿼리가 주어질 때마다 쿼리의 답을 한 줄에 하나씩 출력한다.

제한

노트

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

• 연결 요소 내 두 정점을 연결하는 경로가 항상 존재한다.
• 연결 요소에 포함되는 정점과 포함되지 않는 정점을 연결하는 경로가 존재하지 않는다.