<h1>题目描述</h1>

题目链接
有 $n$ 个航班依次起飞，一个时刻只能有一个飞机起飞，并且有 $m$ 个限制:

1. 第一种限制，第 $i$ 个飞机必须在 $c_i$ 的时刻前起飞。
2. 第二种限制，第 $i$ 个飞机必须在第 $j$ 个飞机之前起飞。
   询问:
3. 一个可行的起飞方案。
4. 每个飞机最早的起飞时间。
   $ n \leq 2 \times 10^3, m \leq 10^4$

<h1>题解</h1>

首先这是一道十分套路的反图拓扑排序。
举例：如果想求出一张有向图中标号 $x$ 的节点最靠前的拓扑序，怎么求？
显然不能开个堆直接跑，这是字典序最小的不保证 $x$ 在最前面，但是我们如果建出反图在反图跑最大字典序的话，就一定能让 $x$ 尽量朝后，答案就是把这个反图拓扑序列 reverse 一下。
那么对于第一问，我们按照第二种限制建出反图，显然第一种的每个限制就变成了每一个航班在拓扑序中的位置 $ pos >n-c_i $，然后按照第一种限制将节点扔到小根堆里跑一边拓扑排序最后 reverse 一下就可以了。
对于第二问，我们考虑在反图中遍历到 $x$ 节点的时候，一直等到有一个约束失效的时候在让 $x$ 入队，这样就能保证 $x$ 尽量靠后（reverse 后尽量靠前）。
时间复杂度瓶颈在于第二种询问，为 $O(n^2)$

<h1>代码</h1>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2000+5;
const int MAXM = 10000+5;

struct Node{
    struct Edge *firstEdge;
    int du,num;
}node[MAXN];

struct Edge{
    Node s,t;
    Edge *next;
}pool[MAXM],*frog = pool;

Edge New(Node s,Node *t){
    t->du++;
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v){
    node[u].firstEdge = New(&node[u],&node[v]);
}

int N,M;
int d[MAXN];
#define P std::pair<int,Node *>
#define MP std::make_pair
std::priority_queue<P,std::vector<P>,std::greater<P> > q;
std::vector<int> ans;

inline void topsort(){
    FOR(i,1,N) if(!node[i].du) q.push(MP(N-d[i],&node[i]));
    while(!q.empty()){
        Node *v = q.top().second;q.pop();
        ans.push_back(v->num);
        //DEBUG(v->num);DEBUG(v->firstEdge);
        for(Edge *e = v->firstEdge;e;e = e->next){
            if(!--e->t->du) q.push(MP(N-d[e->t->num],e->t));
        }
    }
    ROF(i,N-1,0) printf("%d ",ans[i]);puts("");
}

int t[MAXN];

inline int calc(int x){
    int cnt = 0;
    while(!q.empty()) q.pop(); // q.clear();
    FOR(i,1,N) node[i].du = t[i];
    FOR(i,1,N) if(!node[i].du) q.push(MP(N-d[i],&node[i]));
    while(!q.empty()){
        Node *v = q.top().second;q.pop();
        if(v == &node[x]) continue;
        if(N-cnt > d[v->num]) return N - cnt;
        cnt++;
        for(Edge *e = v->firstEdge;e;e = e->next){
            if(!--e->t->du) q.push(MP(N-d[e->t->num],e->t));
        }
    }
    return N - cnt;
}

int main(){
    read(N);read(M);
    FOR(i,1,N) read(d[i]),node[i].num = i;
    FOR(i,1,M){ 
        int u,v;read(u);read(v);
        add(v,u);
    }
    FOR(i,1,N) t[i] = node[i].du;
    topsort();
    FOR(i,1,N) printf("%d ",calc(i));puts("");
    return 0;
}