喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。（图文摘自：http://news.xrxxw.com/newsshow-8018.html）

一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。

输入格式：

输入第一行给出3个正整数n、m和k，其中n（≤10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（≤10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：

依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：

7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7

输出样例：

2
6
4
0

代码长度限制

16 KB

时间限制

150 ms

内存限制

64 MB

栈限制

8192 KB

Java实现：

/**
 * 【喊山】
 * 1. 算法：BFS（广度优先搜索）。因为信号是按层扩散的，BFS 天然适合找“最远距离”。
 * 2. 存储：每个山头最多连2个。直接开 int[N+1][2] 存邻接点。
 * 3. 逻辑：对于每个查询，跑一遍 BFS，记录最大层数 maxLevel 和该层中最小的编号 minID。
 */

import java.io.*;
import java.util.*;

public class Main {
    static int[][] adj; // 存储邻接关系
    static int[] degree; // 记录每个点的度数
    static int n, m, k;

    public static void main(String[] args) throws Exception {
        FastReader fr = new FastReader(System.in);
        n = fr.nextInt();
        m = fr.nextInt();
        k = fr.nextInt();

        // 既然题目说了每个山头最多连2个邻近山头
        adj = new int[n + 1][2];
        degree = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int u = fr.nextInt();
            int v = fr.nextInt();
            adj[u][degree[u]++] = v;
            adj[v][degree[v]++] = u;
        }

        StringBuilder out = new StringBuilder();
        int[] queue = new int[n + 1];
        int[] level = new int[n + 1]; // 记录层数/距离

        for (int i = 0; i < k; i++) {
            int start = fr.nextInt();
            out.append(solve(start, queue, level)).append("\n");
        }
        System.out.print(out);
    }

    private static int solve(int start, int[] queue, int[] level) {
        // 重置状态：-1 代表未访问
        Arrays.fill(level, -1);
        
        int head = 0, tail = 0;
        queue[tail++] = start;
        level[start] = 0;

        int maxLevel = 0;
        int minID = 0;

        while (head < tail) {
            int u = queue[head++];

            // 信号传导到了新的一层
            if (level[u] > maxLevel) {
                maxLevel = level[u];
                minID = u;
            } else if (level[u] == maxLevel && level[u] != 0) {
                // 同一层，找编号最小的
                if (minID == 0 || u < minID) {
                    minID = u;
                }
            }

            // 遍历邻接点
            for (int i = 0; i < degree[u]; i++) {
                int v = adj[u][i];
                if (level[v] == -1) {
                    level[v] = level[u] + 1;
                    queue[tail++] = v;
                }
            }
        }
        
        // 若除了自己没传给任何人，输出0
        return (maxLevel == 0) ? 0 : minID;
    }


    static class FastReader {
        private InputStream in;
        private byte[] buf = new byte[1024 * 16];
        private int ptr = 0, len = 0;

        public FastReader(InputStream in) { this.in = in; }

        private int read() throws Exception {
            if (ptr < len) return buf[ptr++];
            len = in.read(buf);
            ptr = 0;
            return len <= 0 ? -1 : buf[ptr++];
        }

        public int nextInt() throws Exception {
            int c = read(), res = 0;
            while (c >= 0 && c <= 32) c = read();
            if (c == -1) return -1;
            while (c >= '0' && c <= '9') {
                res = res * 10 + (c - '0');
                c = read();
            }
            return res;
        }
    }
}