int postIndex;
int[] inOrder;
int[] postOrder;
Map<Integer, Integer> idxMap = new HashMap<>();

public TreeNode buildTree(int[] inorder, int[] postorder) {
    this.inOrder = inorder;
    this.postOrder = postorder;
    postIndex = postOrder.length - 1;
    int idx = 0;
    for (Integer val : inOrder) {   //将中序遍历的结果存储在map中，方便根据值查找下标
        idxMap.put(val, idx++);
    }
    return createTree(0, inOrder.length - 1);
}

public TreeNode createTree(int inLeft, int inRight) {
    if (inLeft > inRight) {
        return null;
    }
    int rootVal = postOrder[postIndex];
    TreeNode node = new TreeNode(rootVal);
    int index = idxMap.get(rootVal);
    postIndex--;
    node.right = createTree(index + 1, inRight);    //先右后左
    node.left = createTree(inLeft, index - 1);
    return node;
}

int preIndex;
int[] inOrder;
int[] preOrder;
Map<Integer, Integer> idxMap = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    this.inOrder = inorder;
    this.preOrder = preorder;
    preIndex = 0;           //初始值不一样，前序遍历是从前往后
    int idx = 0;
    for (Integer val : inOrder) {
        idxMap.put(val, idx++);
    }
    return createTree(0, inOrder.length - 1);
}

public TreeNode createTree(int inLeft, int inRight) {
    if (inLeft > inRight) {
        return null;
    }
    int rootVal = preOrder[preIndex];
    TreeNode node = new TreeNode(rootVal);
    int index = idxMap.get(rootVal);
    preIndex++;
    node.left = createTree(inLeft, index - 1);      //先左后右
    node.right = createTree(index + 1, inRight);
    return node;
}

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}

public int countNodes2(TreeNode root) {
    TreeNode l = root, r = root;
    // 记录左、右子树的高度
    int hl = 0, hr = 0;
    while (l != null) {
        l = l.left;
        hl++;
    }
    while (r != null) {
        r = r.right;
        hr++;
    }
    // 如果左右子树的高度相同，则是一棵满二叉树
    if (hl == hr) {
        return (int)Math.pow(2, hl) - 1;
    }
    // 如果左右高度不同，则按照普通二叉树的逻辑计算
    return 1 + countNodes(root.left) + countNodes(root.right);
}

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    return preSerialize(root, "");
}

public String preSerialize(TreeNode node, String str) {
    if (node == null) {
        str += "null,";
        return str;
    }
    str += String.valueOf(node.val + ",");
    str = preSerialize(node.left, str);
    str = preSerialize(node.right, str);
    return str;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] strArr = data.split(",");
    List<String> dataList = new LinkedList<>(Arrays.asList(strArr));
    return preDeserialize(dataList);
}

public TreeNode preDeserialize(List<String> dataList) {
    if (dataList.size() == 0) {
        return null;
    }
    if (dataList.get(0).equals("null")) {
        dataList.remove(0);
        return null;
    }
    TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
    dataList.remove(0);
    root.left = preDeserialize(dataList);
    root.right = preDeserialize(dataList);
    return root;
}

public String serialize(TreeNode root) {
    if (root == null) {
        return "";
    }
    StringBuilder sb = new StringBuilder("");
    Deque<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.pollFirst();
        if (node != null) {
            sb.append(node.val).append(",");
            queue.offerLast(node.left);
            queue.offerLast(node.right);
        } else {
            sb.append("null,");
        }
    }
    sb.deleteCharAt(sb.length() - 1);
    return sb.toString();
}

public TreeNode deserialize(String data) {
    if (data == null || data.length() == 0) {
        return null;
    }
    String[] vals = data.split(",");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    Deque<TreeNode> queue = new LinkedList<>();
    queue.offerLast(root);
    int idx = 1;
    while (!queue.isEmpty()) {
        TreeNode node = queue.pollFirst();
        if (!"null".equals(vals[idx])) {
            node.left = new TreeNode(Integer.parseInt(vals[idx]));
            queue.offerLast(node.left);
        }
        idx++;
        if (!"null".equals(vals[idx])) {
            node.right = new TreeNode(Integer.parseInt(vals[idx]));
            queue.offerLast(node.right);
        }
        idx++;
    }
    return root;
}

/**
 * 递归解法
 *
 * @param n
 * @return
 */
public int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}


/**
 * 带备忘录的解法
 * 自顶向下
 */
public int fib1(int n) {
    int[] memory = new int[n + 1];
    return helper(n, memory);
}

private int helper(int n, int[] memory) {
    if (n == 0 || n == 1) {
        return n;
    }
    if (memory[n] != 0) {
        return memory[n];
    }
    memory[n] = helper(n - 1, memory) + helper(n - 2, memory);
    return memory[n];
}


/**
 * dp数组的迭代解法
 * 自底向上
 */
public int fib2(int n) {
    if (n == 0) {
        return 0;
    }
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

/**
 * 优化空间
 */
public int fib3(int n) {
    if (n == 0) {
        return 0;
    }
    int preVal = 0;
    int curVal = 1;
    int sum = 0;
    for (int i = 2; i <= n; i++) {
        sum = curVal+preVal;
        preVal = curVal;
        curVal = sum;
    }
    return curVal;
}

public int maxValue(int[] weights, int[] values, int bag) {
    int n = weights.length;
    int[][] dp = new int[n + 1][bag + 1];
    for (int[] t : dp) {
        Arrays.fill(t, -1);
    }
    return process1(weights, values, 0, bag);
    //return process2(weights, values, 0, bag, dp);
}

/**
 * 递归版本
 *
 * @param weights
 * @param values
 * @param index
 * @param rest
 * @return
 */
public int process1(int[] weights, int[] values, int index, int rest) {
    if (index == weights.length) {
        return 0;
    }
    // p1 代表 不取当前index位置的物品   index之后的所有物品构成的最大价值
    int p1 = process1(weights, values, index + 1, rest);
    int p2 = -1;
    if (rest >= weights[index]) {
        // p2 代表取了当前index位置的物品  以及之后所有物品能构成的最大价值
        p2 = process1(weights, values, index + 1, rest - weights[index]);
        p2 += values[index];

    }
    return Math.max(p1, p2);
}

/**
 * 递归加记忆化搜索，实现中间结果缓存，减少递归调用次数
 *
 * @param weights
 * @param values
 * @param rest    背包剩余容量
 * @param index   物品下标 0 ~ n-1
 *                从当前物品开始以及之后的所有物品，多能构成的最大价值
 * @return
 */
public int process2(int[] weights, int[] values, int index, int rest, int[][] dp) {
    if (index == weights.length) {
        return 0;
    }
    // p1 代表 不取当前index位置的物品   index之后的所有物品构成的最大价值
    int p1;
    if (dp[index + 1][rest] != -1) {
        p1 = dp[index + 1][rest];
    } else {
        p1 = process2(weights, values, index + 1, rest, dp);
    }

    int p2 = -1;
    if (rest >= weights[index]) {
        // p2 代表取了当前index位置的物品  以及之后所有物品能构成的最大价值
        if (dp[index + 1][rest - weights[index]] != -1) {
            p2 = dp[index + 1][rest - weights[index]];
        } else {
            p2 = process2(weights, values, index + 1, rest - weights[index], dp);
            p2 += values[index];
        }
    }
    dp[index][rest] = Math.max(p1, p2);
    return dp[index][rest];
}


/**
 * 动态规划版本
 *
 * @param weights
 * @param values
 * @param bag
 * @return
 */
public int dpWay(int[] weights, int[] values, int bag) {
    int n = weights.length;
    int[][] dp = new int[n + 1][bag + 1];

    //边界值 赋值
    for (int index = n - 1; index >= 0; index--) {
        for (int rest = 0; rest <= bag; rest++) {
            dp[index][rest] = dp[index + 1][rest];
            if (rest - weights[index] >= 0) {
                dp[index][rest] = Math.max(dp[index + 1][rest - weights[index]] + values[index], dp[index][rest]);
            }
        }
    }
    return dp[0][bag];
}

/**
 * 暴力递归解法
 * 状态： 目标金额
 * 选择： 所有硬币的面值
 * 函数的定义： 凑出总金额最少需要的硬币数
 * base cae： amount == 0时，需要0枚硬币，amount < 0时，返回-1
 */
public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    if (amount < 0) {
        return -1;
    }
    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        int subProblem = coinChange(coins, amount - coin);
        if (subProblem == -1) {
            continue;
        }
        res = Math.min(res, subProblem + 1);
    }
    return res == Integer.MAX_VALUE ? -1 : res;
}

/**
 * 带备忘录的解法
 * 自顶向下
 */
int[] memory;
public int coinChange1(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    if (amount < 0) {
        return -1;
    }
    memory = new int[amount + 1];
    Arrays.fill(memory, -2);
    return helper(coins, amount);
}

private int helper(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    if (amount < 0) {
        return -1;
    }
    if (memory[amount] != -2) {
        return memory[amount];
    }
    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        int subProblem = helper(coins, amount - coin);
        if (subProblem == -1) {
            continue;
        }
        res = Math.min(res, subProblem + 1);
    }
    memory[amount] = (res == Integer.MAX_VALUE ? -1 : res);
    return memory[amount];
}

/**
 * dp数组迭代
 * 自底向上
 */
public static int coinChange2(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    if (amount < 0) {
        return -1;
    }
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int i = 0; i < dp.length; i++) {
        for (int coin : coins) {
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

public List<List<String>> res = new ArrayList<>();

public List<List<String>> solveNQueens(int n) {
    int[] record = new int[n];
    int[][] path = new int[n][n];
    func(n, record, 0, path);
    return res;
}

public void func(int n, int[] record, int row, int[][] path) {
    if (row == n) {
        List<String> t = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder("");
            for (int j = 0; j < n; j++) {
                if (path[i][j]==0){
                    sb.append(".");
                }else {
                    sb.append("Q");
                }
            }
            t.add(sb.toString());
        }
        res.add(t);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValidPos(record, row, col)) {
            record[row] = col;
            path[row][col] = 1;
            func(n, record, row + 1, path);
            path[row][col] = 0;
        }
    }
}

public boolean isValidPos(int[] record, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (col == record[i] || Math.abs(row - i) == Math.abs(col - record[i])) {
            return false;
        }
    }
    return true;
}

public static void bubbleSort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    for (int i = array.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
}

public static void swap(int[] array, int i, int j) {
    array[i] = array[i] ^ array[j];
    array[j] = array[i] ^ array[j];
    array[i] = array[i] ^ array[j];
}

public static void selectSort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    for (int i = 0; i < array.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            minIndex = array[j] < array[minIndex] ? j : minIndex;
        }
        swap(array, i, minIndex);
    }
}

public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void insertSort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    for (int i = 1; i < array.length; i++) {
        for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
            swap(array, j, j + 1);
        }
    }
}
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

//   版本一
static int[] nums, tmp;

public static void mergeSortEnter(int[] arr) {
    nums = arr;
    tmp = new int[nums.length];
    mergeSort(0, nums.length - 1);
}

public static void mergeSort(int l, int r) {
    // 终止条件
    if (l >= r) {
        return;
    }
    // 递归划分
    int m = (l + r) / 2;
    mergeSort(l, m);
    mergeSort(m + 1, r);
    // 合并阶段
    int i = l, j = m + 1;
    for (int k = l; k <= r; k++) {
        tmp[k] = nums[k];
    }
    for (int k = l; k <= r; k++) {
        if (i == m + 1) {
            nums[k] = tmp[j++];
        } else if (j == r + 1 || tmp[i] <= tmp[j]) {
            nums[k] = tmp[i++];
        } else {
            nums[k] = tmp[j++];
        }
    }
}


/*
 * 版本二
 */
public static void mergeSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int length = arr.length;
    process(arr, 0, length - 1);
}

public static void process(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}
//将两个有序的片段合并在一起
public static void merge(int[] arr, int L, int mid, int R) {
    int[] helper = new int[R - L + 1];
    int index = 0;
    int p1 = L;
    int p2 = mid + 1;
    while (p1 <= mid && p2 <= R) {
        helper[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) {
        helper[index++] = arr[p1++];
    }
    while (p2 <= R) {
        helper[index++] = arr[p2++];
    }
    for (int i = 0; i < helper.length; i++) {
        arr[L + i] = helper[i];
    }
}

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process(arr, 0, arr.length - 1);
}

public static void process(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int mid = partition(arr, L, R);
    process(arr, L, mid - 1);
    process(arr, mid + 1, R);
}

public static int partition(int[] arr, int L, int R) {
    if (L >= R) {
        return -1;
    }
    //随机选择元素  复杂度为O(nlog(n))
    swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
    int less = L;
    int more = R;
    int cur = L;
    while (cur < more) {
        if (arr[cur] < arr[R]) {
            swap(arr, cur++, less++);
        } else if (arr[cur] == arr[R]) {
            cur++;
        } else {
            swap(arr, cur, --more);
        }
    }
    swap(arr, cur, R);
    return cur;
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 public static void headSort(int[] arr){
        MaxPriorityQueue heap = new MaxPriorityQueue(arr.length);
        for(int i=0;i<arr.length;i++){
            heap.insert(arr[i]);
        }
        int index = 0;
        while(!heap.isEmpty()){
            arr[index++] = heap.delMax();
        }
    }

// 这段代码可以升序打印节点的值
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);   //先遍历左子树
    // 中序遍历代码位置
    print(root.val);
    traverse(root.right);
}

//这段代码可以降序打印节点的值
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 先递归遍历右子树
    traverse(root.right);  // 先遍历右子树
    // 中序遍历代码位置
    print(root.val);
    // 后递归遍历左子树
    traverse(root.left);
}

boolean isInBST(TreeNode root, int target) {
    if (root == null){
        return false;
    }
    if (root.val == target){
        return true;
    }
    //目标值比当前值大，查找右子树
    if (root.val < target) {
        return isInBST(root.right, target);
    }
    //目标值比当前值小，查找左子树
    if (root.val > target){
        return isInBST(root.left, target);
    }
}

TreeNode insertIntoBST(TreeNode root, int val) {
    // 找到空位置插入新节点
    if (root == null){
        return new TreeNode(val);
    }
    if (root.val < val) {
        root.right = insertIntoBST(root.right, val);
    }
    if (root.val > val) {
        root.left = insertIntoBST(root.left, val);
    }
    return root;
}

TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (root.val == key) {
        // 这两个 if 把情况 1 和 2 都正确处理了
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        // 处理情况 3
        TreeNode minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

TreeNode getMin(TreeNode node) {
    while (node.left != null){
        node = node.left;
    }
    return node;
}

public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean validate(TreeNode node, long min, long max) {
    if (node == null) {
        return true;
    }
    if (node.val <= min || node.val >= max) {
        return false;
    }
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}

public class Node {
    /**
     * 拿单词构成的字典树举例来说，因为单词由字母构成，一共26个字母，每个节点需要开辟一个26个长度大小的数组，
     * 用来存储子节点的信息；另外一个字段决定当前是否遍历到字典树结束。
     * pass : 代表所有字符串中通过当前节点的数量
     * end :  代表所有字符串中以当前节点结尾的字符串的数量
     */
    public int pass;
    public int end;
    public Node[] next;

    public Node() {
        this.pass = 0;
        this.end = 0;
        this.next = new Node[26];
    }
}

class Trie{
    
  private Node root = new Node();

  /**
   * 插入一个单词
   */
  public void insert(String word) {
      if (word == null) {
          return;
      }
      char[] str = word.toCharArray();
      Node node = root;
      int index = 0;
      node.pass++;
      for (char c : str) {
          index = c - 'a';
          if (node.next[index] == null) {
              node.next[index] = new Node();
          }
          node = node.next[index];
          node.pass++;
      }
      node.end++;
  }

  /**
   * 查询指定单词出现的次数
   */
  public int search(String word) {
      if (word == null) {
          return 0;
      }
      Node node = root;
      char[] str = word.toCharArray();
      int index = 0;
      for (char c : str) {
          index = c - 'a';
          if (node.next[index] == null) {
              return 0;
          }
          node = node.next[index];
      }
      return node.end;
  }


  public int searchPrefix(String prefix) {
      if (prefix == null) {
          return 0;
      }
      Node node = root;
      char[] str = prefix.toCharArray();
      int index = 0;
      for (char c : str) {
          index = c - 'a';
          if (node.next[index] == null) {
              return 0;
          }
          node = node.next[index];
      }
      return node.pass;
  }

  public void delete(String word) {
      if (search(word) != 0) {
          Node node = root;
          node.pass--;
          char[] str = word.toCharArray();
          int index = 0;
          for (char c : str) {
              index = c - 'a';
              if (--node.next[index].pass == 0) {
                  node.next[index] = null;
                  return;
              }
              node = node.next[index];
          }
          node.end--;
      }
  }
}

/**
 * 大顶堆
 */
public class MaxPriorityQueue {

    private int[] queue;
    private int N = 0;

    private MaxPriorityQueue(int cap) {
        //索引0不用，所以多一个位置，方便计算父子节点位置
        queue = new int[cap + 1];
    }
    //返回当前队列的最大元素
    private int max() {
        return queue[1];
    }
    //父节点索引位置
    private int parent(int node) {
        return node / 2;
    }
    //左子节点索引位置
    private int left(int node) {
        return node * 2;
    }
    //右子节点索引位置
    private int right(int node) {
        return node * 2 + 1;
    }

    /**
     * 插入一个元素的操作，先将元素置为末尾，然后执行上浮操作
     */
    public void insert(int val) {
        N++;
        queue[N] = val;
        swim(N);
    }

    /**
     * 删除堆顶元素，将数组末尾元素放在堆顶，然后执行下沉操作
     */
    public int delMax() {
        int max = queue[1];
        exch(1, N);
        //设置无效
        queue[N] = Integer.MAX_VALUE;
        N--;
        sink(1);
        return max;
    }

    /**
     * 上浮第k个元素
     * 不断比较子节点和父节点的大小，如果父节点小于子节点就相互交换
     */
    private void swim(int k) {
        while (k > 1 && less(parent(k), k)) {
            exch(parent(k), k);
            k = parent(k);
        }
    }

    /**
     * 下沉第k个元素
     * 循环条件索引位置没有超过数组末尾
     * 1. 先比较左右子节点位置的元素，找出较大的元素
     * 2. 如果较大的元素没有位置k的元素大，则下沉操作结束
     * 3. 如果较大的元素比位置k的元素大，则交换两个位置的元素，k指向交换后的位置，继续进行下沉操作
     */
    private void sink(int k) {
        while (left(k) <= N) {
            int older = left(k);
            if (right(k) <= N && less(older, right(k))) {
                older = right(k);
            }
            if (less(older, k)) {
                break;
            }
            exch(older, k);
            k = older;
        }
    }

    private void exch(int i, int j) {
        int tmp = queue[i];
        queue[i] = queue[j];
        queue[j] = tmp;
    }

    private boolean less(int i, int j) {
        return queue[i] < queue[j];
    }
}

public static class Node<V> {
    V value;

    public Node(V v) {
        value = v;
    }
}

public static class UnionSet<V> {
    public Map<V, Node<V>> nodes;
    public Map<Node<V>, Node<V>> parents;
    public Map<Node<V>, Integer> sizeMap;

    public UnionSet(List<V> values) {
        this.nodes = new HashMap<>();
        this.parents = new HashMap<>();
        this.sizeMap = new HashMap<>();
        for (V v : values) {
            Node<V> node = new Node<>(v);
            nodes.put(v, node);
            parents.put(node, node);
            sizeMap.put(node, 1);
        }
    }
        
    public Node<V> findFather(Node<V> cur) {
        Stack<Node<V>> path = new Stack<>();
        while (cur != parents.get(cur)) {
            path.push(cur);
            cur = parents.get(cur);
        }
        //扁平化处理 优化时间复杂度，findFather方法调用越频繁，时间复杂度越接近O(1)
        while (!path.isEmpty()) {
            parents.put(path.pop(), cur);
        }
        return cur;
    }


    //查询两个节点是否是同一个集合
    public boolean isSameSet(V a, V b) {
        if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
            return false;
        }
        return findFather(nodes.get(a)) == findFather(nodes.get(b));
    }

    //合并两个节点所在的集合
    public void union(V a, V b) {
        if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
            return;
        }
        Node<V> aHead = findFather(nodes.get(a));
        Node<V> bHead = findFather(nodes.get(b));
        if (aHead != bHead) {
            int aSetSize = sizeMap.get(aHead);
            int bSetSize = sizeMap.get(bHead);
            Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
            Node<V> small = big == aHead ? bHead : aHead;
            parents.put(small, big);
            sizeMap.put(big, aSetSize + bSetSize);
            sizeMap.remove(small);
        }
    }
}

// 图的表示
public class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;

    public Graph() {
        this.nodes = new HashMap<>();
        this.edges = new HashSet<>();
    }
}
//节点有下标、入度、出度、指向的邻居节点、相关联的边
public class Node {
    public int value;
    public int in;
    public int out;
    public List<Node> nexts;
    public List<Edge> edges;

    public Node(int value) {
        this.value = value;
        this.in = 0;
        this.out = 0;
        this.nexts = new ArrayList<>();
        this.edges = new ArrayList<>();
    }
}

//有向边，边有权重，同时记录边的起点和终点
public class Edge {
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

public void bfs(Node node) {
    if (node == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();
    queue.add(node);
    set.add(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        for (Node n : cur.nexts) {
            if (!set.contains(n)) {
                queue.add(n);
                set.add(n);
            }
        }
    }
}

public void dfs(Node node) {
    if (node == null) {
        return;
    }
    Stack<Node> st = new Stack<>();
    Set<Node> set = new HashSet<>();
    st.push(node);
    set.add(node);
    System.out.println(node.value);
    while (!st.isEmpty()) {
        Node cur = st.pop();
        for (Node n : node.nexts) {
            if (!set.contains(n)) {
                st.push(cur);
                st.push(n);
                set.add(n);
                System.out.println(n.value);
                break;
            }
        }
    }
}

public List<Node> topology(Graph graph) {
    List<Node> result = new ArrayList<>();
    Map<Node, Integer> inMap = new HashMap<>();
    Queue<Node> zeroInQueue = new LinkedList<>();
    for(Node node : graph.nodes.values()){
        inMap.put(node,node.in);
        if(node.in == 0){
            zeroInQueue.offer(node);
        }
    }
    while(!zeroInQueue.isEmpty()){
        Node cur = zeroInQueue.poll();
        result.add(cur);
        for(Node next : cur.nexts){
            inMap.put(next,inMap.get(next)-1);
            if(inMap.get(next) == 0){
                zeroInQueue.offer(next);
            }
        }
    }
    return result;
}