Constrained Topological Sort

#include <bits/stdc++.h>
using namespace std;
 
void fail() {
	cout << "No\n";
	exit(0);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, M;
	cin >> N >> M;
	vector<vector<int>> out(N), in(N);
	for (int i = 0; i < M; ++i) {
		int s, t;
		cin >> s >> t;
		--s, --t;
		out.at(s).push_back(t);
		in.at(t).push_back(s);
	}
 
	// hallamos un orden topológico
	vector<int> order;
	vector<int> indeg(N);
	for (int i = 0; i < N; ++i) {
		indeg.at(i) = size(in.at(i));
		if (!indeg.at(i)) order.push_back(i);
	}
	for (int i = 0; i < size(order); ++i) {
		int s = order.at(i);
		for (int t : out.at(s)) {
			if (!(--indeg.at(t))) order.push_back(t);
		}
	}
	if (size(order) != N) fail();
 
	struct Bound {
		int l, r;
	};
	vector<Bound> bounds(N);
	for (auto &b : bounds) cin >> b.l >> b.r;
	for (int i = N - 1; i >= 0; --i) {
		int t = order.at(i);
		for (int s : in.at(t)) bounds.at(s).r = min(bounds.at(s).r, bounds.at(t).r - 1);
	}
 
	// asignamos etiquetas en orden
	using pi = pair<int, int>;
	priority_queue<pi, vector<pi>, greater<pi>> by_l, by_r;
	// para cada vértice i no asignado con grado de entrada 0
	// guardamos o bien {l[i], i} en by_l o {r[i], i} en by_r
	for (int i = 0; i < N; ++i) {
		indeg.at(i) = size(in.at(i));
		if (!indeg.at(i)) by_l.push({bounds.at(i).l, i});
	}
	vector<int> P(N);
	for (int p = 1; p <= N; ++p) {
		while (!by_l.empty() && by_l.top().first <= p) {
			// pasamos de by_l a by_r
			int v = by_l.top().second;
			by_l.pop();
			by_r.push({bounds.at(v).r, v});
		}
		if (by_r.empty() || by_r.top().first < p) fail();
		int v = by_r.top().second;
		by_r.pop();
		P.at(v) = p;
		for (int t : out.at(v)) {
			if (!(--indeg.at(t))) by_l.push({bounds.at(t).l, t});
		}
	}
 
	cout << "Yes\n";
	for (int i = 0; i < N; ++i) cout << P.at(i) << " ";
}