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 Solution{
  	static int[] p, rank, setSize, col;
  	static int numSets,N;
  	static void preDSU(int n) {
  		N=n;
  		p = new int[numSets = N];
  		rank = new int[N];
  		setSize = new int[N];
  		col=new int[N];
  	}
  	static void addNode(int idx,int c){
  		p[idx]=idx;
  		setSize[idx]=1;
  		col[idx]=c;
  	}
  	static int findSet(int i) { return p[i] == i ? i : (p[i] = findSet(p[i])); }
  
  	static boolean isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  
  	static boolean unionSet(int i, int j)
  	{
  		if (isSameSet(i, j))
  			return false;
  		numSets--;
  		int x = findSet(i), y = findSet(j);
  		col[y]=col[x];
  		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]++;
  		}
  		return true;
  	}
  	static void main() throws Exception{
  		int q=sc.nextInt();
  		HashMap<Integer,Integer>colToNode=new HashMap<>();
  		preDSU(q+7);
  		LinkedList<Integer>indices=new LinkedList<>();
  		for(int i=0;i<q;i++){
  			if(sc.nextInt()==1){
  				indices.add(i);
  				int col=sc.nextInt();
  				addNode(i,col);
  				if(colToNode.containsKey(col)){
  					unionSet(colToNode.get(col),i);
  				}
  				colToNode.put(col,findSet(i));
  			}
  			else{
  				int x=sc.nextInt(),y=sc.nextInt();
  				if(!colToNode.containsKey(x))continue;
  				if(!colToNode.containsKey(y)){
  					addNode(i,y);
  					colToNode.put(y,i);
  				}
  				unionSet(colToNode.get(y),colToNode.get(x));
  				colToNode.put(y,findSet(colToNode.get(y)));
  				if(x!=y)
  					colToNode.remove(x);
  			}
  		}
  		while(!indices.isEmpty())pw.print(col[findSet(indices.pollFirst())]+" ");
  	}
  	public static void main(String[] args) throws Exception{
  		sc=new MScanner(System.in);
  //		sc=new MScanner(" .in");
  		pw = new PrintWriter(System.out);
  		int tc=1;
  //        tc=sc.nextInt();
  		for(curt=1;curt<=tc;curt++) {
  //			pw.printf("Case #%d:", curt);
  			main();
  		}
  
  		pw.flush();
  	}
  	static int curt;
  	static PrintWriter pw;
  	static MScanner sc;
  	static class MScanner {
  		StringTokenizer st;
  		BufferedReader br;
  		public MScanner(InputStream system) {
  			br = new BufferedReader(new InputStreamReader(system));
  		}
  
  		public MScanner(String file) throws Exception {
  			br = new BufferedReader(new FileReader(file));
  		}
  
  		public String next() throws IOException {
  			while (st == null || !st.hasMoreTokens())
  				st = new StringTokenizer(br.readLine());
  			return st.nextToken();
  		}
  		public int[] intArr(int n) throws IOException {
  			int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
  			return in;
  		}
  		public long[] longArr(int n) throws IOException {
  			long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
  			return in;
  		}
  		public int[] intSortedArr(int n) throws IOException {
  			int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
  			shuffle(in);
  			Arrays.sort(in);
  			return in;
  		}
  		public long[] longSortedArr(int n) throws IOException {
  			long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
  			shuffle(in);
  			Arrays.sort(in);
  			return in;
  		}
  		public Integer[] IntegerArr(int n) throws IOException {
  			Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
  			return in;
  		}
  		public Long[] LongArr(int n) throws IOException {
  			Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
  			return in;
  		}
  		public String nextLine() throws IOException {
  			return br.readLine();
  		}
  
  		public int nextInt() throws IOException {
  			return Integer.parseInt(next());
  		}
  
  		public double nextDouble() throws IOException {
  			return Double.parseDouble(next());
  		}
  
  		public char nextChar() throws IOException {
  			return next().charAt(0);
  		}
  
  		public long nextLong() throws IOException {
  			return Long.parseLong(next());
  		}
  
  		public boolean ready() throws IOException {
  			return br.ready();
  		}
  
  		public void waitForInput() throws InterruptedException {
  			Thread.sleep(3000);
  		}
  
  	}
  	static void dbg(int[]in) {
  		System.out.println(Arrays.toString(in));
  	}
  	static void dbg(long[]in) {
  		System.out.println(Arrays.toString(in));
  	}
  	static void sort(int[]in) {
  		shuffle(in);
  		Arrays.sort(in);
  	}
  	static void sort(long[]in) {
  		shuffle(in);
  		Arrays.sort(in);
  	}
  	static void shuffle(int[]in) {
  		for(int i=0;i<in.length;i++) {
  			int idx=(int)(Math.random()*in.length);
  			int tmp=in[i];
  			in[i]=in[idx];
  			in[idx]=tmp;
  		}
  	}
  	static void shuffle(long[]in) {
  		for(int i=0;i<in.length;i++) {
  			int idx=(int)(Math.random()*in.length);
  			long tmp=in[i];
  			in[i]=in[idx];
  			in[idx]=tmp;
  		}
  	}
  }