第 4 题 Putovanje (putovanje)

时间限制 1.0 s · 空间限制 256 MB · 139 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 putovanje.in，输出文件 putovanje.out。

译自 COCI 2023/2024 Contest #4 T4 「Putovanje」

题目描述

Malnar 先生终于迎来了他的年假。他决定要去的国家可以表示为 $n$ 个城市和 $m$ 条双向连接它们的道路。每条道路的长度相同，并且可以通过这些道路从任何一个城市到达另一个城市。从城市 $a$ 到城市 $b$ 的路径被定义为一系列道路，满足从城市 $a$ 开始，按照该序列依次遍历道路，最终到达城市 $b$。路径的长度定义为该路径上的道路数量。

Malnar 先生像以往一样预订了其中一个城市最贵的酒店，然后开始规划他的旅程。为了方便规划，他记录了从酒店到每个城市的最短路径长度。

由于对他期待已久的假期感到兴奋，Malnar 先生完全忘记了酒店位于哪个城市。他当然不想错过这次旅行，所以他请你确定酒店可能位于哪些城市。

输入格式

第一行两个整数 $n$ 和 $m$（$1 \le n \le 5 \cdot 10^4$, $n - 1 \le m \le 10^5$），分别表示城市和道路的数量。

接下来 $m$ 行，每行两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n, u_i \neq v_i$），表示城市 $u_i$ 和 $v_i$ 之间有一条道路。任意两城市之间最多只有一条道路。

最后一行有 $n$ 个整数，第 $i$ 个整数 $d_i$（$-1 \le d_i < n$）表示从城市 $i$ 到酒店所在城市的路径长度，如果 Malnar 先生没有记录这个值，则为 $-1$。

输出格式

第一行输出酒店可能位于多少个城市。

第二行输出酒店可能位于的城市编号，按升序输出。

样例

样例 1

输入：

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

输出：

2
4 6

样例 2

输入：

6 6
1 2
2 3
3 4
4 5
5 6
6 1
2 -1 -1 1 -1 -1

输出：

2
3 5

样例 3

输入：

4 3
1 2
2 3
3 4
1 -1 -1 1

输出：

0

提示

样例解释 1

从城市 4 到城市 1 的路径长度为 2，到城市 7 的路径长度为 3。因此，城市 4 满足两个条件，酒店可以位于那里。

同样的情况也适用于城市 6。

子任务