问题描述:据美国动物分类学家欧内斯特,迈尔推算,世界上有超过10万种动物,各 种动物有自己的语言。假设动物A可以与动物B进行通信,但它不能与动物C通信,动物 C只能与动物B通信,所以动物A、C之间的通信需要动物B来当翻译。问两个动物之间 相互通信至少需要多少个翻译。 测试数据中第1行包含两个整数n(2≤≤200 00)、m(1≤m≤30 0),其中n代表 动物的数量,动物编号从0开始,n个动物编号为0~n—1,m表示可以互相通信的动物对 数,接下来的m行中包含两个数字,分别代表两种动物可以互相通信。再接下来包含一个 整数k（k≤20),代表查询的数量,每个查找包含两个数字,表示这两个动物想要与对方 通信。 编写程序,对于每个查询,输出这两个动物彼此通信至少需要多少个翻译,若它们之间 无法通过翻译来通信,输出一1。要求用JAVA代码 使用分枝限界法实现

以下是使用分枝限界法实现的 JAVA 代码：

import java.util.*;

public class Main {

    static int n, m, k;
    static int[] father;
    static boolean[] vis;

    static class Node implements Comparable<Node> {
        int a, b, cost;

        public Node(int a, int b, int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return cost - o.cost;
        }
    }

    static int find(int x) {
        if (x != father[x]) {
            father[x] = find(father[x]);
        }
        return father[x];
    }

    static void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) {
            father[fa] = fb;
        }
    }

    static boolean isConnect(int a, int b) {
        return find(a) == find(b);
    }

    static int bfs(int start, int end, List<Integer>[] graph) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        vis[start] = true;
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (cur == end) {
                    return level;
                }
                for (int next : graph[cur]) {
                    if (!vis[next]) {
                        vis[next] = true;
                        queue.offer(next);
                    }
                }
            }
            level++;
        }
        return -1;
    }

    static int solve(int start, int end, List<Integer>[] graph) {
        vis = new boolean[n];
        int ans = bfs(start, end, graph);
        if (ans != -1) {
            return ans;
        }

        PriorityQueue<Node> queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            if (isConnect(start, i)) {
                for (int j = 0; j < n; j++) {
                    if (!isConnect(end, j)) {
                        queue.offer(new Node(i, j, 1));
                    }
                }
            }
        }

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            union(cur.a, cur.b);
            int cost = bfs(start, end, graph);
            if (cost != -1) {
                return cur.cost + cost;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }

        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a].add(b);
            graph[b].add(a);
            union(a, b);
        }

        k = scanner.nextInt();
        for (int i = 0; i < k; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if (!isConnect(a, b)) {
                System.out.println("-1");
            } else {
                System.out.println(solve(a, b, graph));
            }
        }
    }
}