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.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  import java.util.*;
  
  public class Main {
      // Graph
      // prefix sums
      //inputs
      public static void main(String args[])throws Exception{
          Input sc=new Input();
          precalculates p=new precalculates();
          StringBuilder sb=new StringBuilder();
          int q=sc.readInt();
          int j=0;
          int m=500005;
          ArrayList<LinkedList> lst=new ArrayList<>(m);
  //        LinkedList ls=new LinkedList();
  //        ls.insert(ls,9);
  //        ls.insert(ls,10);
  //        System.out.println(ls.tail.next);
          HashMap<Integer,LinkedList> map=new HashMap<>();
          int count=0;
          for(int i=0;i<q;i++){
              int d[]=sc.readArray();
              int val=d[1];
              if(d[0]==1){// add
                  if(map.containsKey(val)){
                      //Node n=new Node(count);
                      LinkedList l=map.get(val);
                      l.insert(l,count);
                  }else{
                      //Node n=new Node(count);
                      LinkedList l=new LinkedList();
                      l.insert(l,count);
                      map.put(val,l);
                  }
                  count++;
              }else{
                  if(d[1]==d[2])
                      continue;
                  if(map.containsKey(d[1])){
                      int val2=d[2];
                      if(map.containsKey(d[2])){
                          LinkedList l=map.get(val2);
                          node nn=map.get(val).tail;
                          l.tail.next=map.get(val).head;
                          l.tail=nn;
                          map.remove(val);
                      }else{
                          map.put(val2,map.get(val));
                          map.remove(val);
                      }
                  }
              }
          }
          int arr[]=new int[count];
          for(Integer i:map.keySet()){
              LinkedList l=map.get(i);
              node temp=l.head;
              while(temp!=null){
                  arr[temp.data]=i;
                  temp=temp.next;
              }
          }
          for(int i=0;i<count;i++){
              sb.append(arr[i]+" ");
          }
          sb.append("\n");
          System.out.print(sb);
      }
  }
  class node {
  
      int data;
      node next;
  
      // Constructor
      public node(int d) {
          data = d;
          next = null;
      }
  }
  class LinkedList {
  
      node head;
      node tail;
  
  
      public LinkedList insert(LinkedList list, int data) {
          node new_node = new node(data);
          new_node.next = null;
  
          if (list.head == null) {
              list.head = new_node;
              list.tail = new_node;
          } else {
  
              list.tail.next = new_node;
              list.tail = new_node;
          }
  
          return list;
      }
  }
  class Input{
      BufferedReader br;
      StringTokenizer st;
      Input(){
          br=new BufferedReader(new InputStreamReader(System.in));
          st=new StringTokenizer("");
      }
      public int[] readArray() throws Exception{
          st=new StringTokenizer(br.readLine());
          int a[]=new int[st.countTokens()];
          for(int i=0;i<a.length;i++){
              a[i]=Integer.parseInt(st.nextToken());
          }
          return a;
      }
      public long[] readArrayLong() throws Exception{
          st=new StringTokenizer(br.readLine());
          long a[]=new long[st.countTokens()];
          for(int i=0;i<a.length;i++){
              a[i]=Long.parseLong(st.nextToken());
          }
          return a;
      }
      public int readInt() throws Exception{
          st=new StringTokenizer(br.readLine());
          return Integer.parseInt(st.nextToken());
      }
      public long readLong() throws Exception{
          st=new StringTokenizer(br.readLine());
          return Long.parseLong(st.nextToken());
      }
      public String readString() throws Exception{
          return br.readLine();
      }
      public int[][] read2dArray(int n,int m)throws Exception{
          int a[][]=new int[n][m];
          for(int i=0;i<n;i++){
              st=new StringTokenizer(br.readLine());
              for(int j=0;j<m;j++){
                  a[i][j]=Integer.parseInt(st.nextToken());
              }
          }
          return a;
      }
  }
  class precalculates{
      public long gcd(long p, long q) {
          if (q == 0) return p;
          else return gcd(q, p % q);
      }
      public int[] prefixSumOneDimentional(int a[]){
          int n=a.length;
          int dp[]=new int[n];
          for(int i=0;i<n;i++){
              if(i==0)
                  dp[i]=a[i];
              else
                  dp[i]=dp[i-1]+a[i];
          }
          return dp;
      }
      public int[] postSumOneDimentional(int a[]) {
          int n = a.length;
          int dp[] = new int[n];
          for (int i = n - 1; i >= 0; i--) {
              if (i == n - 1)
                  dp[i] = a[i];
              else
                  dp[i] = dp[i + 1] + a[i];
          }
          return dp;
      }
      public int[][] prefixSum2d(int a[][]){
          int n=a.length;int m=a[0].length;
          int dp[][]=new int[n+1][m+1];
          for(int i=1;i<=n;i++){
              for(int j=1;j<=m;j++){
                  dp[i][j]=a[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
              }
          }
          return dp;
      }
      public long pow(long a,long b){
          long mod=1000000007;
          long ans=1;
          if(b<=0)
              return 1;
          if(b%2==0){
              ans=pow(a,b/2)%mod;
              return ((ans%mod)*(ans%mod))%mod;
          }else{
              ans=pow(a,b-1)%mod;
              return ((a%mod)*(ans%mod))%mod;
          }
      }
  
  }
  class GraphInteger{
      HashMap<Integer,vertex> vtces;
      class vertex{
          HashMap<Integer,Integer> children;
          public vertex(){
              children=new HashMap<>();
          }
      }
      public GraphInteger(){
          vtces=new HashMap<>();
      }
      public void addVertex(int a){
          vtces.put(a,new vertex());
      }
      public void addEdge(int a,int b,int cost){
          if(!vtces.containsKey(a)){
              vtces.put(a,new vertex());
          }
          if(!vtces.containsKey(b)){
              vtces.put(b,new vertex());
          }
          vtces.get(a).children.put(b,cost);
  //        vtces.get(b).children.put(a,cost);
      }
      public boolean isCyclicDirected(){
          boolean isdone[]=new boolean[vtces.size()+1];
          boolean check[]=new boolean[vtces.size()+1];
          for(int i=1;i<=vtces.size();i++) {
              if (!isdone[i] && isCyclicDirected(i,isdone, check)) {
                  return true;
              }
          }
          return false;
      }
      private boolean isCyclicDirected(int i,boolean isdone[],boolean check[]){
          if(check[i])
              return true;
          if(isdone[i])
              return false;
          check[i]=true;
          isdone[i]=true;
          Set<Integer> set=vtces.get(i).children.keySet();
          for(Integer ii:set){
              if(isCyclicDirected(ii,isdone,check))
                  return true;
          }
          check[i]=false;
          return false;
      }
  }
  class union_find {
      int n;
      int[] sz;
      int[] par;
  
      union_find(int nval) {
          n = nval;
          sz = new int[n + 1];
          par = new int[n + 1];
          for (int i = 0; i <= n; i++) {
              par[i] = i;
              sz[i] = 1;
          }
      }
  
      int root(int x) {
          if (par[x] == x)
              return x;
          return par[x] = root(par[x]);
      }
  
      boolean find(int a, int b) {
          return root(a) == root(b);
      }
  
      int union(int a, int b) {
          int ra = root(a);
          int rb = root(b);
          if (ra == rb)
              return 0;
          if(a==b)
              return 0;
          if (sz[a] > sz[b]) {
              int temp = ra;
              ra = rb;
              rb = temp;
          }
          par[ra] = rb;
          sz[rb] += sz[ra];
          return 1;
      }
  }
  
  
  
  
  
  
  
  