分析
我们首先想到的自然是根据大小关系建图，在这之后我们跑一遍拓扑排序
但是由于l和r的限制关系我们需要对传统的拓扑排序做一些改变
我们考虑将所有入度为0且现在的拓扑序号已经大于等于l的点放入一个优先队列，这个优先队列以r为关键字从小到大排序，这样我们就可以保证r小的点被排在前面
但是我们发现暴力判断l是否合法是行不通的，于是我们考虑再建一个优先队列，将所有入度为0的点以l为关键字从小到大排序，每次当队首l大于等于当前序号则弹出这个点，将这个点加入到r的那个优先队列中，这样我们就可以保证每个点最多在这个优先队列中进一次出一次
但是我们还要考虑一种情况，如果对于点1和点2，1的值小于2的值但是l[1]<l[2]且r[1]>r[2]则可能1的取值在区间(r[1],r[2])，那这种情况肯定是不合法的，所以我们要在求拓扑序等一众操作之前先对图进行一遍dfs来判断这个图是不是一个DAG并将点i的r值更新为min(l[i],l[I's son])，注意这个值是从后往前一一更新的，来保证对于点i，所有它能到达的点跟i的lr关系均合法
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
int n,m,le[300100],ri[300100],T,d[300100],id[300100],vis[300100],now[300100];
vector<int>v[300100];
priority_queue<pair<int,int> >ql,qr;
inline void dfs(int x){
if(now[x]){
puts("-1");
exit(0);
}else if(vis[x])return;
now[x]=1;
for(int i=0;i<v[x].size();i++){
dfs(v[x][i]);
ri[x]=min(ri[x],ri[v[x][i]]-1);
}
vis[x]=1;
now[x]=0;
}
int main(){
int i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d%d",&le[i],&ri[i]);
for(i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].pb(y);
d[y]++;
ri[x]=min(ri[x],ri[y]);
}
for(i=1;i<=n;i++)
if(!d[i]&&!vis[i])dfs(i);
for(i=1;i<=n;i++)
if(!d[i])ql.push(mp(-le[i],i));
T=1;
while(!ql.empty()&&-ql.top().fi<=T)
qr.push(mp(-ri[ql.top().se],ql.top().se)),ql.pop();
while(!qr.empty()){
int x=qr.top().se;qr.pop();
if(ri[x]<T){
puts("-1");
return 0;
}
id[T]=x;T++;
for(i=0;i<v[x].size();i++)
if(d[v[x][i]]){
d[v[x][i]]--;
if(!d[v[x][i]])ql.push(mp(-le[v[x][i]],v[x][i]));
}
while(!ql.empty()&&-ql.top().fi<=T)
qr.push(mp(-ri[ql.top().se],ql.top().se)),ql.pop();
}
for(i=1;i<=n;i++)if(!id[i]){puts("-1");return 0;}
for(i=1;i<=n;i++)printf("%d
",id[i]);
return 0;
}