题目描述

给出 NNN 个点， MMM 条边的有向图，对于每个点 vvv ，求 A(v)A(v)A(v) 表示从点 vvv 出发，能到达的编号最大的点。

输入输出格式

输入格式：

第1 行，2 个整数 N,MN,MN,M 。

接下来 MMM 行，每行2个整数 Ui,ViU_i,V_iUi​,Vi​ ，表示边 (Ui,Vi)(U_i,V_i)(Ui​,Vi​) 。点用 1,2,⋯,N1, 2,\cdots,N1,2,⋯,N 编号。

输出格式：

N 个整数 A(1),A(2),⋯,A(N)A(1),A(2),\cdots,A(N)A(1),A(2),⋯,A(N) 。

输入输出样例

4 3

1 2

2 4

4 3

4 4 3 4

说明

• 对于60% 的数据， 1≤N.K≤1031 \le N . K \le 10^31≤N.K≤103 ；

• 对于100% 的数据， 1≤N,M≤1051 \le N , M \le 10^51≤N,M≤105 。

/*Code by 520 -- 8.21*/

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define RE register

#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)

using namespace std;

const int N=2e5+;

struct node{

    int u,v;

}e[N];

int n,m,tot,dfn[N],low[N];

int to[N],net[N],h[N],cnt;

int stk[N],top;

int f[N],ans;

int scc,bl[N],val[N],rd[N];

bool ins[N];

int gi(){

    int a=;char x=getchar();

    while(x<''||x>'')x=getchar();

    while(x>=''&&x<='')a=(a<<)+(a<<)+(x^),x=getchar();

    return a;

}

il void add(int u,int v){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt;}

void tarjan(int u){

    dfn[u]=low[u]=++tot,stk[++top]=u,ins[u]=;

    for(RE int i=h[u];i;i=net[i]){

        int v=to[i];

        if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);

        else if(ins[v]) low[u]=min(low[u],dfn[v]);

    }

    if(dfn[u]==low[u]){

        scc++;

        while(stk[top+]!=u)

            bl[stk[top]]=scc,val[scc]=max(val[scc],stk[top]),ins[stk[top--]]=;

    }

}

queue<int>q;

il void init(){

    n=gi(),m=gi();

    For(i,,m) e[i].u=gi(),e[i].v=gi(),add(e[i].u,e[i].v);

    For(i,,n) if(!dfn[i]) tarjan(i);

    memset(h,,sizeof(h)),cnt=;

    For(i,,m) if(bl[e[i].u]!=bl[e[i].v]) add(bl[e[i].v],bl[e[i].u]),rd[bl[e[i].u]]++;

    For(i,,scc) if(!rd[i]) q.push(i),f[i]=val[i];

    while(!q.empty()){

        int u=q.front();q.pop();

        for(RE int i=h[u];i;i=net[i]){

            f[to[i]]=max(f[to[i]],max(f[u],val[to[i]]));

            if(!(--rd[to[i]])) q.push(to[i]);

        }

    }

    For(i,,n) printf("%d ",f[bl[i]]);

}

int main(){

    init();

    return ;

}