旅行商(TSP)

Description

Shrek is a postman working in the mountain, whose routine work is sending mail to n villages. Unfortunately, road between villages is out of repair for long time, such that some road is one-way road. There are even some villages that can’t be reached from any other village. In such a case, we only hope as many villages can receive mails as possible.

Shrek hopes to choose a village A as starting point (He will be air-dropped to this location), then pass by as many villages as possible. Finally, Shrek will arrived at village B. In the travelling process, each villages is only passed by once. You should help Shrek to design the travel route.

Input

There are 2 integers, n and m, in first line. Stand for number of village and number of road respectively.

In the following m line, m road is given by identity of villages on two terminals. From v1 to v2. The identity of village is in range [1, n].

Output

Output maximum number of villages Shrek can pass by.

Example

Input

Output

Restrictions

1 <= n <= 1,000,000

0 <= m <= 1,000,000

These is no loop road in the input.

Time: 2 sec

Memory: 256 MB

Hints

Topological sorting

原理与要点： 按照拓扑排序的方法对图进行遍历，遍历的过程中记录路径长度，取一个最大值即得到答案。
- 预处理出所有点的入度(deg[i])，起初把所有入度为0的点入队
- 取出队头节点x，答案与x的路径长度取一个最大值，对于从x出发的每条边（x,y）把(deg[y])减1。若被减为0，则把y入队，y的路径长度为x的路径长度加1。
- 重复上述步骤直至队列为空，此时所取得的最大值即为答案
遇到的问题：无
时间和空间复杂度： 时间复杂度(O(n+m))，空间复杂度(O(n+m))

#include "cstdio"
#include "cmath"

using namespace std;
const int maxn = 1e6 + 100;
const int mod = 1e6 - 10;

const int SZ = 1<<20;  //快速io
struct fastio{
    char inbuf[SZ];
    char outbuf[SZ];
    fastio(){
        setvbuf(stdin,inbuf,_IOFBF,SZ);
        setvbuf(stdout,outbuf,_IOFBF,SZ);
    }
}io;
int ver[maxn], Next[maxn], head[maxn], deg[maxn];
int tot, n;
int ansmax = 0;
struct node {
    int x, length;
};
node q[maxn];

void add(int x, int y) {
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
    deg[y]++;
}

void topsort() {
    int from = 0, to = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            q[to] = {i, 1};
            to = (to + 1) % mod;
        }
    }
    while (from != to) {
        node x = q[from++];
        from %= mod;
        if (x.length > ansmax) ansmax = x.length;
        for (int i = head[x.x]; i; i = Next[i]) {
            int y = ver[i];
            if (--deg[y] == 0) {
                q[to] = {y, x.length + 1};
                to = (to + 1) % mod;
            }
        }
    }
}

int main() {
    int m;
    scanf("%d %d", &n, &m);
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        add(u, v);
    }
    topsort();
    printf("%d
", ansmax);
    return 0;
}