题意描述

你有一张 $n$ 个点 $m$ 条边的无向连通简单图，每条边的边权都为 $1$。

小 A 选择了一个起始点 $s$，并求出起始点 $s$ 到每个节点 $u$ 的最短路 $d_u$。

小 A 告诉了你所有 $d[u] \bmod 3$ 的值，请你找到所有可能的起始点。

如果不存在，请输出 −1。

输入格式

第一行包含两个整数 $n,m$，表示无向图的点数和边数。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$ ，其中 $a_i \equiv d_i \pmod 3$。

接下来的 $m$ 行，每行包含两个整数 $u_i,v_i$，表示第 $i$ 条无向边的两个端点。

输出格式

共一行，包含所有合法的起始点 $s$，按照升序输出并用一个空格分隔。

如果不存在解，输出一行一个 -1。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围与约定

对于 $50\%$ 的数据，满足 $n,m \le 1000$。

另有 $70\%$ 的数据，满足合法起始点的数量不超过 $55$ 个。

对于 $100\%$ 的数据，满足 $1 \le n, m \le 2 \times 10^6$。

分析

考虑什么样子的点可以作为原点？

对于点 $u$ ，若其可以作为原点，则需满足：

$a[u] = 0$
对于与其直接相连的任意一个点 $v$ ，需要满足 $a[v] = 1$

且图中只能存在一个原点。

故我们找出满足以上条件的点，若有多个显然无解，否则 bfs 判断一下该点到其他点的最短路 $\bmod 3$ 的值是否与 $a$ 数组相同即可。

时间复杂度 $O(n + m)$

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 2000000 + 5;
const int HA = 998244353;

int n , m , d[M];

struct Edge{
    int to , last;
}edge[M << 1];

int edge_num;
int head[M << 1];

I void add_edge(int from , int to) {
    edge[++ edge_num] = (Edge){to , head[from]}; head[from] = edge_num;
    edge[++ edge_num] = (Edge){from , head[to]}; head[to] = edge_num;
}

int dis[M] , inq[M];

void bfs(int sta) {
	queue<int> q;
	clean(dis , 0x3f3f3f3f) , clean(inq , 0);
	
	q.push(sta);
	inq[sta] = 1 , dis[sta] = 0;
	while(!q.empty()) {
		int fro = q.front(); q.pop();
		inq[fro] = 0;
		PE(i , fro) {
			int to = edge[i].to;
			if(dis[to] > dis[fro] + 1) {
				dis[to] = dis[fro] + 1;
				if(!inq[to]) {
					inq[to] = 1;
					q.push(to);
				}
			}
		}
	}
	rep(i , 1 , n) {
	    if(dis[i] % 3 != d[i]) return (void)puts("-1");
	}
	printf("%d\n" , sta);
}

#define LOCAL

int main() {
    #ifdef LOCAL
        freopen("source.in" , "r" , stdin);
        freopen("source.out" , "w" , stdout);
    #endif
    read(n) , read(m);
    rep(i , 1 , n) read(d[i]);
    rep(i , 1 , m) {
        int u , v;
        read(u) , read(v);
        add_edge(u , v);
    }
    int poi = 0;
    rep(x , 1 , n) {
        int flag = 1;
        if(d[x] == 0) {
            PE(i , x) {
                int to = edge[i].to;
                flag &= (d[to] == 1);
            }
        }
        if(flag == 1 && d[x] == 0) {
            poi = x; break;
        }
    }
    if(!poi) puts("-1");
    else bfs(poi);

    return 0;
}