5分 不知道思路哪有问题 求hack

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <iomanip>
#define N 500010

using namespace std;
int n, m, p[N], head[2][N], ver[2][N], nxt[2][N], tot[2]; // 邻接表建边[2]代表边颜色
int circ, v[N], ans[N];  // 连通块个数，Visit[]，答案
queue<int> Maxst[N];  // 记录每个连通块内数值最大点的编号

long long read() {
	long long x = 0, h = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			h = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (long long)(ch - '0');
		ch = getchar();
	}
	return x * h;
}

void add(int x, int y, int tp) { // (出发点，到达点，边的颜色)
	ver[tp][++tot[tp]] = y;
	nxt[tp][tot[tp]] = head[tp][x];
	head[tp][x] = tot[tp];
}

void get_circle(int st, int id) {  // 通过起始点找到此连通块所有点
	queue<int> q;
	while (!q.empty())
		q.pop();
	int maxx = p[st];
	Maxst[id].push(st);
	q.push(st);
	v[st] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int k = 0; k <= 1; k++) {
			for (int i = head[k][x]; i; i = nxt[k][i]) {
				int y = ver[k][i];
				if (v[y])
					continue;

				// label y
				v[y] = 1;
				// queue
				q.push(y);
				// Maxst
				if (p[y] > maxx) {
					while (!Maxst[id].empty())
						Maxst[id].pop();
					Maxst[id].push(y);
				} else if (p[y] == maxx)
					Maxst[id].push(y);
			}
		}
	}
}

void get_ans(int id) {  // 通过bfs更新一个连通块内所有的答案
	queue<pair<int, int> > q;
	while (!q.empty())
		q.pop();
	while (!Maxst[id].empty()) {
		int x = Maxst[id].front();
		Maxst[id].pop();
		ans[x] = 0;  // 最大值处答案为0
		q.push(make_pair(x, 2));  // 从最大点出发到任何点需要交换一次，所以颜色是特殊的2，保证第一次更新与颜色不一样
	}
	while (!q.empty()) {
		int x = q.front().first;
		int ltp = q.front().second;
		q.pop();
		for (int k = 0; k <= 1; k++) {   // 枚举不同颜色的边
			for (int i = head[k][x]; i; i = nxt[k][i]) {
				int y = ver[k][i];
				if (y == x)
					continue;
				if (ans[y] > ans[x] + (k != ltp)) {   // 判断更新条件
					ans[y] = ans[x] + (int)(k != ltp);
					q.push(make_pair(y, k));
				}
			}
		}
	}
}

int main() {
	n = read();
	m = read();
	for (int i = 1; i <= n; i++)
		p[i] = read(), ans[i] = 99999999;

	for (int i = 1; i <= m; i++) {
		int u = read();
		int v = read();
		if (u == v)
			continue;
		add(u, v, 0);  // 题目中的图
		add(v, u, 1);  // 建立的所有边反向的图
	}
	while (1) {
		int st = 0;
		for (int i = 1; i <= n; i++) {
			if (!v[i]) {
				st = i;
				break;
			}
		}
		if (!st)   // 是否有没被统计的连通块
			break;
		circ++;  // 记录环数
		get_circle(st, circ);  // 统计连通块
	}
	for (int i = 1; i <= circ; i++) // 分别计算每个连通块的答案
		get_ans(i);
	for (int i = 1; i <= n; i++) {
		printf("%d ", ans[i]);
	}
	return 0;
}