Replace the Numbers

题意翻译

维护一个数列，这个数列初始为空。 对于这个数列，总共有 $q$ 次操作，每次操作分为如下两个种类： 1. `1 x`，意为在数列末尾加一个数字 2. `2 x y`，意为将数列中所有值为 $x$ 的数的值替换成 $y$ 请在 $q$ 次操作后，输出这个数列。 $1\leqslant q,x,y\leqslant5*10^5$

题目描述

You have an array of integers (initially empty). You have to perform $ q $ queries. Each query is of one of two types: - " $ 1 $ $ x $ " — add the element $ x $ to the end of the array; - " $ 2 $ $ x $ $ y $ " — replace all occurrences of $ x $ in the array with $ y $ . Find the resulting array after performing all the queries.

输入输出格式

输入格式

The first line contains a single integer $ q $ ( $ 1 \le q \le 5 \cdot 10^5 $ ) — the number of queries. Next $ q $ lines contain queries (one per line). Each query is of one of two types: - " $ 1 $ $ x $ " ( $ 1 \le x \le 5 \cdot 10^5 $ ); - " $ 2 $ $ x $ $ y $ " ( $ 1 \le x, y \le 5 \cdot 10^5 $ ). It's guaranteed that there is at least one query of the first type.

输出格式

In a single line, print $ k $ integers — the resulting array after performing all the queries, where $ k $ is the number of queries of the first type.

输入输出样例

输入样例 #1

7
1 3
1 1
2 1 2
1 2
1 1
1 2
2 1 3

输出样例 #1

3 2 2 3 2

输入样例 #2

4
1 1
1 2
1 1
2 2 2

输出样例 #2

1 2 1

输入样例 #3

8
2 1 4
1 1
1 4
1 2
2 2 4
2 4 3
1 2
2 2 7

输出样例 #3

1 3 3 7

说明

In the first example, the array changes as follows: $ [] $ $ \rightarrow $ $ [3] $ $ \rightarrow $ $ [3, 1] $ $ \rightarrow $ $ [3, 2] $ $ \rightarrow $ $ [3, 2, 2] $ $ \rightarrow $ $ [3, 2, 2, 1] $ $ \rightarrow $ $ [3, 2, 2, 1, 2] $ $ \rightarrow $ $ [3, 2, 2, 3, 2] $ . In the second example, the array changes as follows: $ [] $ $ \rightarrow $ $ [1] $ $ \rightarrow $ $ [1, 2] $ $ \rightarrow $ $ [1, 2, 1] $ $ \rightarrow $ $ [1, 2, 1] $ . In the third example, the array changes as follows: $ [] $ $ \rightarrow $ $ [] $ $ \rightarrow $ $ [1] $ $ \rightarrow $ $ [1, 4] $ $ \rightarrow $ $ [1, 4, 2] $ $ \rightarrow $ $ [1, 4, 4] $ $ \rightarrow $ $ [1, 3, 3] $ $ \rightarrow $ $ [1, 3, 3, 2] $ $ \rightarrow $ $ [1, 3, 3, 7] $ .