Replace the Numbers
Contest: Educational Codeforces Round 119 (Rated for Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, data structures, dsu, implementation

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
7
1 3
1 1
2 1 2
1 2
1 1
1 2
2 1 3

Example output:
3 2 2 3 2

Example input:
4
1 1
1 2
1 1
2 2 2

Example output:
1 2 1

Editorial:
Let's solve the problem from the end. Let's maintain the array $$$p_x$$$ — what number will $$$x$$$ become if we apply to it all the already considered queries of type $$$2$$$. If the current query is of the first type, then we simply add $$$p_x$$$ to the resulting array. If the current query is of the second type, then we have to change the value of $$$p_x$$$. Since all occurrences of $$$x$$$ must be replaced with $$$y$$$, it is enough to assign $$$p_x = p_y$$$.
Since we process each query in $$$O(1)$$$, the final complexity is $$$O(n)$$$.
There is also an alternative solution. Let's process queries in the direct order. Let's store all its positions in an array for each number. Then for the first query, it is enough to put the index in the corresponding array of positions. And for a query of the second type, we have to move all the positions of the number $$$x$$$ into an array of positions of the number $$$y$$$. The naive implementation is obviously too slow, but we can use the small to large method, then the complexity of the solution will be $$$O(n \log{n})$$$.