记录编号	259807	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]奖学金	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2016-05-11 17:37:19	内存使用	0.54 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("reward.in","r",stdin);freopen("reward.out","w",stdout);chul();Cu
using namespace std;
const int maxn=20010;
struct op{
	int to,next;
	op(){
		to=next=0;
	}
};
op t[maxn];
bool sign=0;
int len=0,tot=0,colour=0;
int p[maxn>>1]/*每人价钱*/,h[maxn>>1]/*head*/,color[maxn>>1],d[maxn>>1]/*出度*/;
bool flag[maxn>>1];
void chul();
void mem();
int max(int,int);
void dfs(int);
void insert(int,int);
int main(){
	Begin;
} 
void chul(){
	mem();
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		insert(x,y);
	}
	for(int i=1;i<=n;i++){
		if(d[i]==0){
			colour++;
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		tot+=p[i];
	}
	if(colour==0){
		printf("impossible");
		return;
	}
	if(colour>0){
		for(int i=1;i<=n;i++){
			if(color[i]==0){
				printf("impossible");
				return;
			}
		}
	}
	if(!sign)printf("%d",tot+n*100);
}
void mem(){
	memset(p,0,sizeof(p));
	memset(h,-1,sizeof(h));
	memset(color,0,sizeof(color));
	memset(d,0,sizeof(d));
}
void dfs(int x){
	color[x]=-colour;
	for(int i=h[x];i!=-1;i=t[i].next){
		int r=t[i].to;
		if(color[r]<0){
			printf("impossible");
			sign=1;
			exit(0);
		}
		dfs(r);
		p[x]=max(p[x],p[r]+1);
	}
	color[x]=colour;
}
void insert(int x,int y){
	len++;
	t[len].to=y;
	t[len].next=h[x];
	d[y]++;
	h[x]=len;
}
int max(int x,int y){
	if(x>y)return x;
	return y;
}