멋진 연결 요소와 쿼리

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

그래프 $G$는 간선이 없고, 각 정점은 빨간색 또는 파란색이다. $G$에 다음 세 종류의 쿼리를 차례로 수행하는 프로그램을 작성하여라. 각 쿼리는 그 이전 쿼리들이 남긴 상태에 대해 수행된다.

• 1 u v: 서로 다른 두 정점 u와 v를 잇는 간선을 추가한다. 가능하다면, 이 간선을 포함하는 연결 요소의 정점 색을 0개 이상 바꿔 멋진 연결 요소로 만든다. 방법이 여러 가지라면 색을 가장 적게 바꾸는 방법을 택한다.
• 2 u: 정점 u를 포함하는 연결 요소에 있는 모든 정점의 색을 바꾼다.
• 3 c: G에 있는 멋진 연결 요소 중 색 c인 정점이 가장 많은 연결 요소를 고른다. c가 0이면 빨간색, 1이면 파란색을 뜻한다. 고른 연결 요소에 속한 정점 번호 중 가장 작은 번호를 출력한다.

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

둘째 줄에 1번부터 $N$번까지 정점의 색 $c_1, c_2, \cdots, c_N$이 공백으로 구분되어 주어진다. 0은 빨간색, 1은 파란색 정점을 뜻한다.

셋째 줄부터 $Q$개의 줄에 쿼리가 주어진다. 1번 쿼리에서 고른 두 정점 u와 v 사이에는 간선이 없다. 1번 쿼리를 수행하는 방법이 유일한 입력만 주어진다. 3번 쿼리는 하나 이상 주어지며, 멋진 연결 요소가 있을 때만 주어진다. 3번 쿼리의 답이 유일한 입력만 주어진다.

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

연결 요소는 간선으로 연결된 부분 그래프이다. 엄밀하게는 다음 두 조건을 만족하는 정점 집합을 연결 요소라고 한다.

• 연결 요소 안의 두 정점을 잇는 경로가 항상 존재한다.
• 연결 요소에 속한 정점과 속하지 않은 정점을 잇는 경로가 존재하지 않는다.