description: 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
  
  The first line contains a single integer q (1 ≤ q ≤ 5 ⋅ 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 ≤ x ≤ 5 ⋅ 10^5); 
    * "2 x y" (1 ≤ x, y ≤ 5 ⋅ 10^5). 
  
  
  
  It's guaranteed that there is at least one query of the first type.
  
  Output
  
  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.
  
  Examples
  
  Input
  
  
  7
  1 3
  1 1
  2 1 2
  1 2
  1 1
  1 2
  2 1 3
  
  
  Output
  
  
  3 2 2 3 2 
  
  Input
  
  
  4
  1 1
  1 2
  1 1
  2 2 2
  
  
  Output
  
  
  1 2 1 
  
  Input
  
  
  8
  2 1 4
  1 1
  1 4
  1 2
  2 2 4
  2 4 3
  1 2
  2 2 7
  
  
  Output
  
  
  1 3 3 7 
  
  Note
  
  In the first example, the array changes as follows:
  
  [] → [3] → [3, 1] → [3, 2] → [3, 2, 2] → [3, 2, 2, 1] → [3, 2, 2, 1, 2] → [3, 2, 2, 3, 2].
  
  In the second example, the array changes as follows:
  
  [] → [1] → [1, 2] → [1, 2, 1] → [1, 2, 1].
  
  In the third example, the array changes as follows:
  
  [] → [] → [1] → [1, 4] → [1, 4, 2] → [1, 4, 4] → [1, 3, 3] → [1, 3, 3, 2] → [1, 3, 3, 7].
solution: import java.util.*;
  import java.io.*;
  
  public class Template {
  	
  	static Scanner sc = new Scanner(System.in);
  	static PrintWriter pw = new PrintWriter(System.out);
  
  	// Union-Find Disjoint Sets Library written in OOP manner, using both path
  	// compression and union by rank heuristics
  	static class UnionFind {
  		int[] p, rank, setSize;
  		int numSets;
  
  		public UnionFind(int N) {
  			p = new int[numSets = N];
  			rank = new int[N];
  			setSize = new int[N];
  			for (int i = 0; i < N; i++) {
  				p[i] = i;
  				setSize[i] = 1;
  			}
  		}
  
  		public int findSet(int i) {
  			return p[i] == i ? i : (p[i] = findSet(p[i]));
  		}
  
  		public boolean isSameSet(int i, int j) {
  			return findSet(i) == findSet(j);
  		}
  
  		public void unionSet(int i, int j) {
  			if (isSameSet(i, j))
  				return;
  			numSets--;
  			int x = findSet(i), y = findSet(j);
  			if (rank[x] > rank[y]) {
  				p[y] = x;
  				setSize[x] += setSize[y];
  			} else {
  				p[x] = y;
  				setSize[y] += setSize[x];
  				if (rank[x] == rank[y])
  					rank[y]++;
  			}
  		}
  
  		public int numDisjointSets() {
  			return numSets;
  		}
  
  		public int sizeOfSet(int i) {
  			return setSize[findSet(i)];
  		}
  	}
  
  	public static void main(String[] args) throws Exception {
  		int t = 1;
  		int n = (int) (5 * 1e5) + 5;
  		int cnt = 0;
  		UnionFind dsu = new UnionFind(n);
  		int q = sc.nextInt();
  
  		int repIdx[] = new int[n]; // each value make it have a representitive idx that currently has that
  		//value default 0
  		int parentval[] = new int[n];
  		while (t-- > 0) {
  
  			for (int i = 0; i < q; i++) {
  				int x = sc.nextInt();
  				if (x == 1) {
  					int v = sc.nextInt();
  					if (repIdx[v] == 0) {
  						repIdx[v] = ++cnt;
  
  					} else {
  						dsu.unionSet(repIdx[v], ++cnt);
  					}
  					parentval[dsu.findSet(cnt)] = v;
  
  				} else {
  					int xx = sc.nextInt();
  					int y = sc.nextInt();
  					if(xx == y)continue;
  					if (repIdx[xx] == 0)
  						continue;
  					if (repIdx[y] == 0) {
  
  					} else
  						dsu.unionSet(repIdx[xx], repIdx[y]);
                      repIdx[y] = repIdx[xx];
  					parentval[dsu.findSet(repIdx[xx])] = y;
                      repIdx[xx]=0;
                      	}
  
  			}
  
  		}
  		for (int i = 1; i <= cnt; i++) {	
  			int val = parentval[dsu.findSet(i)];
  			pw.print(val + " ");
  		}
  
  		pw.close();
  
  	}
  
  	// --------------------stuff ----------------------
  	static class pair implements Comparable<pair> {
  		int v;
  		int w;
  
  		public pair(int v, int w) {
  			this.v = v;
  			this.w = w;
  
  		}
  
  		public int compareTo(pair p) {
  			return this.w - p.w;// increasing order!!
  
  			// return Double.compare(v*w, p.w*p.v);
  
  		}
  	}
  
  	static class Scanner {
  		StringTokenizer st;
  		BufferedReader br;
  
  		public Scanner(InputStream s) {
  			br = new BufferedReader(new InputStreamReader(s));
  		}
  
  		public Scanner(FileReader r) {
  			br = new BufferedReader(r);
  		}
  
  		public String next() throws IOException {
  			while (st == null || !st.hasMoreTokens())
  				st = new StringTokenizer(br.readLine());
  			return st.nextToken();
  		}
  
  		public int nextInt() throws IOException {
  			return Integer.parseInt(next());
  		}
  
  		public long nextLong() throws IOException {
  			return Long.parseLong(next());
  		}
  
  		public String nextLine() throws IOException {
  			return br.readLine();
  		}
  
  		public double nextDouble() throws IOException {
  			String x = next();
  			StringBuilder sb = new StringBuilder("0");
  			double res = 0, f = 1;
  			boolean dec = false, neg = false;
  			int start = 0;
  			if (x.charAt(0) == '-') {
  				neg = true;
  				start++;
  			}
  			for (int i = start; i < x.length(); i++)
  				if (x.charAt(i) == '.') {
  					res = Long.parseLong(sb.toString());
  					sb = new StringBuilder("0");
  					dec = true;
  				} else {
  					sb.append(x.charAt(i));
  					if (dec)
  						f *= 10;
  				}
  			res += Long.parseLong(sb.toString()) / f;
  			return res * (neg ? -1 : 1);
  		}
  
  		public long[] nextlongArray(int n) throws IOException {
  			long[] a = new long[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextLong();
  			return a;
  		}
  
  		public Long[] nextLongArray(int n) throws IOException {
  			Long[] a = new Long[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextLong();
  			return a;
  		}
  
  		public int[] nextIntArray(int n) throws IOException {
  			int[] a = new int[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextInt();
  			return a;
  		}
  
  		public Integer[] nextIntegerArray(int n) throws IOException {
  			Integer[] a = new Integer[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextInt();
  			return a;
  		}
  
  		public boolean ready() throws IOException {
  			return br.ready();
  		}
  	}
  
  }