关于为何bfs第一个出来的不是正确解：

dist[u]一定是最小的，但是dist[v]却不一定，根据三角不等式，dist[v]<=dist[u]+1。 由于我们的答案是两者取一个max，所以答案只会是dist[u]或者dist[u]+1。

普通的宽搜，队列中的点的权值是一定具有二段性和单调性的。

也就是类似：x, x, x, ..., x, x + 1, x + 1, ..., x + 1。

反证法容易证明这一结论。

现在的u是队首，dist[u]=x。

可能会存在一种情况：

当前点 $u->a$, $dist[a]=x+1$， 后面有一个点 $y$, $dist[y]=x$，$y->b$, $dist[b]=x$。 这样第一次搜到的点就不是最优解了。

但是，我们会发现，如果ans==x，那么就一定是最优解了。因为这时ans已经是可能的最小值了。（优化1）

同理，当队首的dist已经变成x+1，且ans=x+1，也就不用继续搜了。因为此时ans一定大于等于x+1。

所以，加上优化1，代码还可以变成这样（题解里貌似没有）：

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1000010, M = 4000010;

int h[N], e[M], ne[M], idx;
int n, m, k;
int dist[N], q[N], q0[N];
int fa[N], sz[N];
bool vis[M];

int get(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = get(fa[x]);
}

void merge(int x, int y)
{
	fa[x] = y;
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{  
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &m, &k);

    if (m == n - 1)
    {
        printf("Poor D!\n");
        return 0;
    }

    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    memset(dist, 0x3f, sizeof dist);
	queue<PII> q;
    while (k -- )
    {
        int x;
        scanf("%d", &x);
        dist[x] = 0;
        q.push({x, M});
    }

	for (int i = 1; i <= n; i ++ ) fa[i] = i;

	int ans = 2e9;
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		int u = t.x, from = t.y ^ 1;
        if (dist[u] >= ans) break;
		for (int i = h[u]; ~i; i = ne[i])
		{
			if (i == from) continue;
			if (vis[i]) continue;
			vis[i] = vis[i ^ 1] = true;
			int v = e[i];
			if (dist[v] > dist[u] + 1)
			{
				dist[v] = dist[u] + 1;
				fa[get(v)] = get(u);
				q.push({v, i});
			}
			else if (get(u) == get(v))
			{
				ans = min(ans, max(dist[u], dist[v]));
                if (ans == dist[u]) break; // 优化1
			}
			else fa[get(u)] = get(v);
		}
	}
	printf("%d\n", ans);
	
    return 0;
}