28092번 - 우선순위와 쿼리

문제

1,2,ドル\cdots,N$으로 번호가 매겨진 $N$개의 정점이 있다. 이때, 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.

• 1 u v: 정점 $u$와 $v$를 잇는 간선을 추가한다. 이때 $u,v$는 모두 삭제되지 않은 정점임이 보장되며 같은 간선은 최대 1번만 주어진다. $(1 \le u,v \le N)$
• 2: 정점의 개수가 가장 많은 트리를 선택한다. 정점의 개수가 가장 많은 트리가 두 개 이상 존재할 경우에는 가장 번호가 작은 정점끼리 비교하여 번호가 더 작은 트리를 선택한다. 그 후 선택한 트리에서 가장 번호가 작은 정점의 번호를 출력하고, 그 트리의 간선과 정점을 모두 삭제한다.

입력

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

입력으로 주어지는 모든 수는 정수이다.

출력

2번 쿼리가 주어질 때마다 트리에서 가장 번호가 작은 정점의 번호를 출력한다. 2번 쿼리는 최소 1개 주어지며, 트리가 없는데 2번 쿼리가 주어지는 경우는 없다.

제한

힌트