22996번 - 유니온 파인드 복원 스페셜 저지

문제

준원이는 스타팅 포인트의 멤버이다. 준원이는 회사에서 병합 (merge) 연산을 수행할 때마다 포인트를 얻는다.

그래서 준원이는 C언어로 다음과 같은 코드를 작성했다.

#include <stdio.h>
int par[300001];
int find(int v) {
 if (v == par[v]) return v;
 return par[v] = find(par[v]);
}
void merge(int u, int v){
 u = find(u);
 v = find(v);
 if (u != v) par[u] = v;
}
int main() {
 int N, Q;
 scanf("%d %d", &N, &Q);
 for (int i=1; i<=N; i++) par[i] = i;
 for (int i=1; i<=Q; i++) {
 int type;
 scanf("%d", &type);
 if(type == 1) {
 int u, v;
 scanf("%d %d", &u, &v);
 merge(u, v);
 }
 else if(type == 2) {
 int v;
 scanf("%d", &v);
 printf("%d\n", find(v));
 }
 }
}

준원이는 위 코드로 다음 문제를 풀었다.

1ドル$부터 $N$까지 $N$개의 자연수를 원소로 가지는 $N$개의 집합 $\{1\}, \{2\}, \cdots , \{N\}$이 있다.

여러분은 아래와 같이 주어지는 질의를 순서대로 $Q$개 처리해야 한다.

• 1번 질의: 1 u v 의 형식으로 주어진다. 원소 $u$가 속한 집합과 원소 $v$가 속한 집합이 다르다면, 두 집합을 하나로 합친다.
• 2번 질의: 2 v 의 형식으로 주어진다. 원소 $v$가 속한 집합에 있는 원소를 아무거나 하나 반환한다.

그런데, 문제가 생겼다. 준원이는 어떤 입력 데이터를 받았는지 까먹었다. 하지만 주어진 $N, Q$ 값과, 2번 질의들이 반환한 값들, 그리고 실행 결과 최종 상태에서의 par[] 배열의 값들은 기억하고 있다.

이 정보를 이용해 어떤 입력 데이터가 주어졌을지 복원해보자.

입력

첫째 줄에 준원이가 기억하는 원소의 개수 $N$과 질의의 개수 $Q$가 공백으로 구분되어 주어진다.

둘째 줄에 실행 결과 최종 상태에서의 par[] 배열의 값들을 의미하는 $N$개의 자연수가 공백으로 구분되어 주어진다.

셋째 줄에 입력 데이터에서 주어진 2번 질의의 개수 $M$이 주어진다.

넷째 줄부터 $M$개의 줄에 걸쳐, 준원이의 코드가 2번 질의들이 반환한 값들이 한 줄에 하나씩 순서대로 주어진다.

출력

준원이의 프로그램이 받았을 입력 데이터를 아래와 같은 형식으로 복원하여 출력한다.

첫째 줄에 원소의 개수 $N$과 질의의 개수 $Q$를 공백으로 구분하여 출력한다.

둘째 줄부터 $Q$개의 줄에 걸쳐, 질의를 한 줄에 하나씩 순서대로 출력한다.

• 1번 질의: 1 u v 의 형식으로 출력한다.
• 2번 질의: 2 v 의 형식으로 출력한다.

준원이가 기억하는 정보와 일치하는 입력 데이터가 여러 가지 있으면 아무거나 출력해도 된다.

제한

• 1ドル \leq N \leq 300,000円$
• 1ドル \leq M \leq Q \leq 300,000円$
• 1번 질의에서 1ドル \leq u, v \leq N$
• 1번 질의에서 $u, v$는 같을 수 있다.
• 2번 질의에서 1ドル \leq v \leq N$
• 준원이가 기억하는 정보와 일치하는 입력 데이터가 존재한다.

힌트