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.io.*;
  import java.util.*;
  public class E {
  	public static void main(String[] args) {
  		try {
  			System.setIn(new FileInputStream("input.txt"));
  			System.setOut(new PrintStream(new FileOutputStream("output.txt")));
  		} catch (Exception e) {
  			System.err.println(e.toString());
  		}
  		Scanner sc = new Scanner(System.in);
  		int tc = 1;
  		for(int ti = 1; ti <= tc; ti++) {
  			int len = sc.nextInt();
  			DJS djs = new DJS(len);
  			for(int i = 0; i < len; i++) {
  				int kk = sc.nextInt();
  				if(kk == 1) {
  					int x = sc.nextInt();
  					djs.add(x);
  				} else {
  					int x = sc.nextInt();
  					int y = sc.nextInt();
  					djs.change(x, y);
  				}
  			}
  			System.out.println(djs.getResult());
  		}
  	}
  
  	static class DJS {
  		int[] par;
  		int[] rank;
  		int st = 0;
  		int[] val;
  		List<Integer> list = new ArrayList<>();
  		public DJS(int len) {
  			par = new int[len+1];
  			for(int i = 0; i <= len; i++)
  				par[i] = i;
  			val = new int[500005];
  			rank = new int[len+1];
  			list.add(0);
  		}
  
  		public int find(int ind) {
  			if(par[ind] == ind)
  				return ind;
  			int pp = find(par[ind]);
  			par[ind] = pp;
  			return pp;
  		}
  
  		public int union(int ind1, int ind2, int vv) {
  			int par1 = find(ind1);
  			int par2 = find(ind2);
  			list.set(par1, vv);
  			list.set(par2, vv);
  			if(par1 == par2)
  				return par1;
  			if(rank[par1] >= rank[par2]) {
  				rank[par1]++;
  				par[par2] = par1;
  				return par1;
  			} else {
  				rank[par2]++;
  				par[par1] = par2;
  				return par2;
  			}
  		}
  
  
  		public void add(int vv) {
  			st++;
  			list.add(vv);
  			if(val[vv] == 0) {
  				val[vv] = st;
  			} else {
  				union(val[vv], st, vv);
  			}
  		}
  
  		public void change(int x, int y) {
  			if(x == y)
  				return;
  			if(val[x] == 0)
  				return;
  			if(val[y] == 0) {
  				val[y] = find(val[x]);
  				list.set(val[y], y);
  			} else {
  				union(val[y], val[x], y);
  			}
  			val[x] = 0;
  		}
  
  		public String getResult() {
  			StringBuilder sb = new StringBuilder();
  			for(int i = 1; i <= st; i++) {
  				int pp = find(par[i]);
  				sb.append(list.get(pp)+ " ");
  			}
  			return sb.toString();
  		}
  	}
  }