题目描述

给定 $n$ 个点 $m$ 条边的无权无向连通图，以及一组取值为 $0,1,2$ 的序列 $d_1 \dots d_n$，求以哪些点为起点时，到点 $i=1 \dots n$ 的最短路径长度模 $3$ 正好等于 $d_i$。

输入格式

第 $1$ 行 $2$ 个正整数 $n, m$； 后 $m$ 行每行两个整数 $u_i, v_i$ 表示一条边； 后 $1$ 行 $n$ 个正整数 $d_1 \dots d_n$。

输出格式

第 $1$ 行 $1$ 个非负整数 $C$ 表示有多少种可能的起点； 第 $2$ 行 $C$ 个正整数表示可能的起点的编号，从小到大顺序输出。

输入输出样例

输入#1

5 5
1 2
2 3
3 4
4 5
4 1
1 0 1 2 0

输出#1

1
2

说明/提示

• $50\%$ 的数据，$n, m \leq 1000$；
• 另 $20\%$ 的数据，$u_i = i, v_i = i+1$；
• $100\%$ 的数据，$1 \leq n,m \leq 10^6$，$0 \leq d_i \leq 2$。

或许能用的原题链接：https://www.mxoj.net/problem/SH240725

完全没有思路啊qwq