题意描述

你有一张 $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

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

Output ‘s eg

2

数据范围与约定

对于 $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;
}

THE END