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 E {
      class Node {
          Node next;
          int pos;
  
          public Node(int p) {
              pos = p;
              next = null;
          }
      }
  
      class LinkedList {
          Node head, tail;
  
          public LinkedList() {
              head = new Node(-1);
              tail = head;
          }
      }
  
      final int MAXN = 5000001;
  
      public void prayGod() throws IOException {
          int q = nextInt();
  
          HashMap<Integer, LinkedList> data = new HashMap<>();
          int pos = 0;
  
          for (int zzz = 0; zzz < q; zzz++) {
              int op = nextInt();
              switch (op) {
                  case 1: {
                      int x = nextInt();
                      if (!data.containsKey(x))
                          data.put(x, new LinkedList());
                      data.get(x).tail.next = new Node(pos++);
                      data.get(x).tail = data.get(x).tail.next;
                      break;
                  }
                  case 2: {
                      int x = nextInt();
                      int y = nextInt();
                      if (x == y)
                          continue;
                      if (!data.containsKey(x) || data.get(x).head.next == null)
                          continue;
                      if (!data.containsKey(y))
                          data.put(y, new LinkedList());
                      data.get(y).tail.next = data.get(x).head.next;
                      data.get(y).tail = data.get(x).tail;
                      data.get(x).head.next = null;
                      data.get(x).tail = data.get(x).head;
                      break;
                  }
                  default: {
                      System.exit(1);
                  }
              }
          }
  
          int[] ret = new int[pos];
          Arrays.fill(ret, -1);
  
          for (int key : data.keySet()) {
              Node ptr = data.get(key).head.next;
              while (ptr != null) {
                  ret[ptr.pos] = key;
                  ptr = ptr.next;
              }
          }
  
          for (int i = 0; i < pos; i++) {
              out.printf("%d ", ret[i]);
          }
          out.println();
  
      }
  
      public void printVerdict(boolean verdict) {
          if (verdict)
              out.println(VERDICT_YES);
          else
              out.println(VERDICT_NO);
      }
  
      static final String VERDICT_YES = "YES";
      static final String VERDICT_NO = "NO";
      static final boolean RUN_TIMING = true;
      static final boolean AUTOFLUSH = false;
      static final boolean FILE_INPUT = false;
      static final boolean FILE_OUTPUT = false;
  
      static int iinf = 0x3f3f3f3f;
      static long inf = (long) 1e18 + 10;
      static long mod = (long) 1e9 + 7;
  
      static char[] inputBuffer = new char[1 << 20];
      static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1 << 20);
      static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), AUTOFLUSH);
  
      // int data-type
      public int nextInt() throws IOException {
          return Integer.parseInt(next());
      }
  
      public int[] nextIntArray(int n) throws IOException {
          int[] arr = new int[n];
          for (int i = 0; i < n; i++)
              arr[i] = nextInt();
          return arr;
      }
  
      public void sort(int[] a) {
          shuffle(a);
          Arrays.sort(a);
      }
  
      public static void printArray(int[] arr) {
          for (int i = 0; i < arr.length; i++)
              out.print(arr[i] + " ");
          out.println();
      }
  
      // long data-type
      public long nextLong() throws IOException {
          return Long.parseLong(next());
      }
  
      public long[] nextLongArray(int n) throws IOException {
          long[] arr = new long[n];
          for (int i = 0; i < n; i++)
              arr[i] = nextLong();
          return arr;
      }
  
      public static void printArray(long[] arr) {
          for (int i = 0; i < arr.length; i++)
              out.print(arr[i] + " ");
          out.println();
      }
  
      public void sort(long[] a) {
          shuffle(a);
          Arrays.sort(a);
      }
  
      // double data-type
      public double nextDouble() throws IOException {
          return Double.parseDouble(next());
      }
  
      public double[] nextDoubleArray(int n) throws IOException {
          double[] arr = new double[n];
          for (int i = 0; i < n; i++)
              arr[i] = nextDouble();
          return arr;
      }
  
      public static void printArray(double[] arr) {
          for (int i = 0; i < arr.length; i++)
              out.print(arr[i] + " ");
          out.println();
      }
  
      // Generic type
      public <T> void sort(T[] a) {
          shuffle(a);
          Arrays.sort(a);
      }
  
      public static <T> void printArray(T[] arr) {
          for (int i = 0; i < arr.length; i++)
              out.print(arr[i] + " ");
          out.println();
      }
  
      public String next() throws IOException {
          int len = 0;
          int c;
          do {
              c = in.read();
          } while (Character.isWhitespace(c) && c != -1);
          if (c == -1) {
              throw new NoSuchElementException("Reached EOF");
          }
          do {
              inputBuffer[len] = (char) c;
              len++;
              c = in.read();
          } while (!Character.isWhitespace(c) && c != -1);
          while (c != '\n' && Character.isWhitespace(c) && c != -1) {
              c = in.read();
          }
          if (c != -1 && c != '\n') {
              in.unread(c);
          }
          return new String(inputBuffer, 0, len);
      }
  
      public String nextLine() throws IOException {
          int len = 0;
          int c;
          while ((c = in.read()) != '\n' && c != -1) {
              if (c == '\r') {
                  continue;
              }
              inputBuffer[len] = (char) c;
              len++;
          }
          return new String(inputBuffer, 0, len);
      }
  
      public boolean hasNext() throws IOException {
          String line = nextLine();
          if (line.isEmpty()) {
              return false;
          }
          in.unread('\n');
          in.unread(line.toCharArray());
          return true;
      }
  
      public void shuffle(int[] arr) {
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int j = (int) (Math.random() * (n - i));
              int temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
  
      public void shuffle(long[] arr) {
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int j = (int) (Math.random() * (n - i));
              long temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
  
      public void shuffle(Object[] arr) {
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int j = (int) (Math.random() * (n - i));
              Object temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
  
      public static void main(String[] args) throws IOException {
          if (FILE_INPUT)
              in = new PushbackReader(new BufferedReader(new FileReader(new File("output.txt"))), 1 << 20);
          if (FILE_OUTPUT)
              out = new PrintWriter(new FileWriter(new File("output.txt")));
  
          long time = 0;
          time -= System.nanoTime();
          new E().prayGod();
          time += System.nanoTime();
  
          if (RUN_TIMING)
              System.err.printf("%.3f ms%n", time / 1000000.0);
  
          out.flush();
          in.close();
      }
  }
  