{"problem":{"name":"[COCI 2023/2024 #4] Putovanje","description":{"content":"Malnar 先生终于迎来了他的年假。他决定要去的国家可以表示为 $n$ 个城市和 $m$ 条双向连接它们的道路。每条道路的长度相同，并且可以通过这些道路从任何一个城市到达另一个城市。从城市 $a$ 到城市 $b$ 的路径被定义为一系列道路，满足从城市 $a$ 开始，按照该序列依次遍历道路，最终到达城市 $b$。路径的长度定义为该路径上的道路数量。 Malnar 先生像以往一样预订了其中一个城市","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10231"},"statements":[{"statement_type":"Markdown","content":"Malnar 先生终于迎来了他的年假。他决定要去的国家可以表示为 $n$ 个城市和 $m$ 条双向连接它们的道路。每条道路的长度相同，并且可以通过这些道路从任何一个城市到达另一个城市。从城市 $a$ 到城市 $b$ 的路径被定义为一系列道路，满足从城市 $a$ 开始，按照该序列依次遍历道路，最终到达城市 $b$。路径的长度定义为该路径上的道路数量。\n\nMalnar 先生像以往一样预订了其中一个城市最贵的酒店，然后开始规划他的旅程。为了方便规划，他记录了从酒店到每个城市的最短路径长度。\n\n由于对他期待已久的假期感到兴奋，Malnar 先生完全忘记了酒店位于哪个城市。他当然不想错过这次旅行，所以他请你确定酒店可能位于哪些城市。\n\n## Input\n\n第一行两个整数 $n$ 和 $m\\ (1\\le n\\le 5\\cdot 10^4,n-1\\le m\\le 10^5)$，分别表示城市和道路的数量。\n\n接下来 $m$ 行，每行两个整数 $u_i,v_i\\ (1\\le u_i,v_i\\le n,u_i\\neq v_i)$，表示城市 $u_i$ 和 $v_i$ 之间有一条道路。任意两城市之间最多只有一条道路。\n\n最后一行有 $n$ 个整数，第 $i$ 个整数 $d_i\\ (-1\\le d_i<n)$ 表示从城市 $i$ 到酒店所在城市的路径长度，如果 Malnar 先生没有记录这个值，则为 $-1$。\n\n## Output\n\n第一行输出酒店可能位于多少个城市。\n\n第二行输出酒店可能位于的城市编号，**按升序输出**。\n\n[samples]\n\n## Background\n\n**译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T4「[Putovanje](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**\n\n## Note\n\n### 样例解释 1\n\n从城市 $4$ 到城市 $1$ 的路径长度为 $2$，到城市 $7$ 的路径长度为 $3$。因此，城市 $4$ 满足两个条件，酒店可以位于那里。\n\n同样的情况也适用于城市 $6$。\n\n### 子任务\n\n| 子任务编号 |                     附加限制                     | 分值 |\n| :--------: | :----------------------------------------------: | :--: |\n|    $1$     | $m+1=n\\le 5\\ 000$，对于所有 $i$ 满足 $u_i+1=v_i$ | $10$  |\n|    $2$     |           对于所有 $i>1$ 满足 $d_i=-1$           | $20$ |\n|    $3$     |                 $n,m\\le 5\\ 000$                  | $35$ |\n|    $4$     |                    无附加限制                    | $45$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10231","tags":["2023","广度优先搜索 BFS","COCI（克罗地亚）","bitset"],"sample_group":[["7 6\n1 2\n1 3\n3 4\n3 5\n3 6\n5 7\n2 -1 -1 -1 -1 -1 3\n","2\n4 6\n"],["6 6\n1 2\n2 3\n3 4\n4 5\n5 6\n6 1\n2 -1 -1 1 -1 -1\n","2\n3 5\n"],["4 3\n1 2\n2 3\n3 4\n1 -1 -1 1\n","0\n"]],"created_at":"2026-03-03 11:09:25"}}