题目背景

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 11 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。

输入格式

第一行，两个正整数 n、m，表示生物种类 n 和吃与被吃的关系数 m。

接下来 mm 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数，为最大食物链数量模上 80112002 的结果。

输入输出样例

输入 #1复制

5 7

1 2

1 3

2 3

3 5

2 5

4 5

3 4

输出 #1复制

5

说明/提示

各测试点满足以下约定：
n<=5000

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

int a,b,n,m,bj[5005][5005],zshu,shu;//对了，用longlong的话空间会炸掉的哦（longlong是8个字节，比int多一倍）

struct hehe

{

	int as,bs,qz;

}sz[5005];//sz[i]表示i的情况（比如天敌有几个，食物有几个，强制末尾是他的食物链有几个）

queue<int>q;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=0;i<m;i++)

	{

		scanf("%d%d",&a,&b);

		sz[a].bs++;//bs是食物数

		sz[b].as++;//as是天敌数

		bj[a][b]=1;//bj[i][j]=1表示i会吃掉j

	}

	for(int i=1;i<=n;i++)//查找食物链的开始节点

	{

		if(sz[i].as==0)//找到啦

		{

			sz[i].qz=1;

			q.push(i);

		}

	}

	while(q.empty()!=true)//只要还有一个节点，while就休想退出！

	{

		shu=q.front();

		for(int i=1;i<=n;i++)

		{

			if(bj[shu][i]==1)//研究表明：第shu号动物会吃掉第i号动物

			{

				sz[i].as--;//把他的天敌-1（就是还需要收集多少个节点的路径数）

				sz[i].qz+=sz[shu].qz;//qz是路径总数的意思。

				sz[i].qz%=80112002;//题目告诉我们要取模（这里不取会40分，别问我怎么知道的）

				if(sz[i].as==0)//符合要求，要不是结尾，要不是下一个。

				{

					if(sz[i].bs==0)//他是结尾

					{

						zshu+=sz[i].qz;//zshu是食物链的总数

						zshu%=80112002;//正常操作，取模

						continue;//他都结尾了加他干嘛？

					}

					q.push(i);//他不是结尾，加进去继续搜

				}

			}

		}

		q.pop();//删除第一个，也就是现在这个

	}

	cout<<zshu<<endl;//输出

	return 0;

}