2022 CCPC桂林 L 拓扑+dp+贪心

题意：已知一个排列某些位置上的数，再给你m个限制$(u,v)(u,v)$，要求，问能不能求出来一种合法的排列。不合法输出-1

解法：跑俩次拓扑序，一次正向，一次反向，求出来每个点的可行域。再进行贪心，用优先队列维护最小的右端点的可行解。赛中比较难想到，想到了就很好写了。

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define set9 fixed<<setprecision(9)
#define set12 fixed<<setprecision(12)
#define set2 fixed<<setprecision(2)
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define db double
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=2e5+5;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll Inverse(ll x) { return qpow(x,mod-2);}

int n,m;
struct node
{
    int l,r,in,out,id;
    bool operator< (const node &x){return l<x.l;}
}a[maxn];
vector<int>g[maxn],g2[maxn];
int p[maxn],vis[maxn];

void init()
{
    rep(i,1,n) a[i].l=1,a[i].r=n,a[i].in=0,a[i].out=0,a[i].id=i,g[i].clear(),g2[i].clear(),vis[i]=0;
}

void topl()
{
    queue<int>q;
    rep(i,1,n) if(a[i].in==0) q.push(i);
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        for(auto v:g[top])
        {
            a[v].in--;
            a[v].l=max(a[v].l,a[top].l+1);
            if(a[v].in==0) q.push(v);
        }
    }
}
void topr()
{
    queue<int>q;
    rep(i,1,n) if(a[i].out==0) q.push(i);
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        for(auto v:g2[top])
        {
            a[v].out--;
            a[v].r=min(a[v].r,a[top].r-1);
            if(a[v].out==0) q.push(v);
        }
    }
}

void solve()
{
    n=read(),m=read();
    init();
    rep(i,1,n)
    {
        p[i]=read();
        if(p[i]>=1) a[i].l=p[i],a[i].r=p[i],vis[p[i]]=1;
    }
    rep(i,1,m)
    {
        int u=read(),v=read();
        a[u].out++;
        a[v].in++;
        g[u].push_back(v);
        g2[v].push_back(u);
    }
    topl();//正向dp求l
    topr();//反向dp求r
    rep(i,1,n)
    {
        if(a[i].l>a[i].r)
        {
            puts("-1");
            return ;
        }
    }
    rep(i,1,n)
    {
        if(a[i].l==a[i].r) vis[a[i].l]=1,p[i]=a[i].l;
    }
    sort(a+1,a+1+n);
    priority_queue<pii,vector<pii>,greater<pii> >q;
    int j=1;
    rep(i,1,n)
    {
        while(j<=n&&a[j].l<=i){ q.push({a[j].r,a[j].id}),j++; }
        if(q.empty())
        {
            puts("-1");
            return;
        }
        auto [val,id]=q.top();
        q.pop();
        if(val<i)
        {
            puts("-1");
            return ;
        }
        p[id]=i;
    }
    rep(i,1,n) printf("%lld ",p[i]);
    puts("");
}


signed main()
{
    int _;_=read();while(_--) solve();
}