<h1>题目</h1>

<h2>题目描述</h2>

小明要去一个国家旅游。这个国家有$ N $个城市，编号为 $ 1 $至$ N $，并且有$ M $条道路连接着，小明准备从其中一个城市出发，并只往东走到城市$ i $停止。

所以他就需要选择最先到达的城市，并制定一条路线以城市$ i $为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。
现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的$ i $，都需要你为小明制定一条路线，并求出以城市$ i $为终点最多能够游览多少个城市。

<h2>输入输出格式</h2>

<h3>输入格式：</h3>

第$ 1$行为两个正整数$ N,M $。

接下来$ M $行，每行两个正整数$ x,y$，表示了有一条连接城市$ x $与城市$ y $的道路，保证了城市$ x $在城市$ y $西面。

<h3>输出格式：</h3>

$ N $行，第$ i $行包含一个正整数，表示以第$ i $个城市为终点最多能游览多少个城市。

<h2>输入输出样例</h2>

<h3>输入样例#1：</h3>

[code lang=text]
5 6
1 2
1 3
2 3
2 4
3 4
2 5
[/code]

<h3>输出样例#1</h3>

[code lang=text]
1
2
3
4
3
[/code]

<h2>说明</h2>

均选择从城市 $ 1 $ 出发可以得到以上答案。

对于 $ 20\% $ 的数据， $ 1 \le N\le 100$ ；

对于 $ 60\% $ 的数据，$ 1\le N\le 1000 $ ；

对于 $100\%$ 的数据， $ 1 \le N \le 100000,1\le M\le 200000 $ 。

<h1>解题报告</h1>

这一题是练习拓扑排序的上手简单题目。

首先，这一题可以用DP来做。但是一个不经过拓扑排序的图有后效性。

经过拓扑排序之后按照拓扑序来进行DP即可。

至于如何动态规划：我们考虑拓扑排序完后，只能从东向西走，那么不妨设$ dp_u $表示以节点u为终点，能经过的最多的城市。这就是一个简单的线性dp，状态转移方程为：

$$ dp_u = Max&#123;dp_v&#125;(u和v连通)$$

详情见代码。

<h1>代码</h1>

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define add(u,v) node[u].firstEdge = New(&node[u],&node[v])

const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;

struct Node;
struct Edge;

int N,M,cnt;
Node* ts[MAXN];

struct Node{
    int ru,dp;
    bool used;
    Edge *firstEdge;
}node[MAXN];

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

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

inline void topsort(){
    std::queue<Node *> q;
    for(int i = 1;i <= N;i++)
        if(!node[i].ru){
            q.push(&node[i]);
            ts[++cnt] = &node[i];
        }
    while(!q.empty()){
        Node *v = q.front();q.pop();
        for(Edge *e = v->firstEdge;e;e = e->next){
            if(!--e->t->ru){
                q.push(e->t);
                ts[++cnt] = e->t;
            }
        }
    }
}

int main(){
    scanf("%d%d",&N,&M);
    for(int u,v,i = 1;i <= M;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        node[v].ru++;
    }
    topsort();
    for(int i = 1;i <= N;i++)
        node[i].dp = 1;
    for(int i = 1;i <= N;i++){
        Node *v = ts[i];
        for(Edge *e = v->firstEdge;e;e = e->next){
            e->t->dp = std::max(e->t->dp,v->dp + 1);
        }
    }
    for(int i = 1;i <= N;i++)
        printf("%dn",node[i].dp);
    return 0;
}