Reward

Dandelion's uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards. 
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a's reward should more than b's.Dandelion's unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work's reward will be at least 888 , because it's a lucky number.

Input

One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000) 
then m lines ,each line contains two integers a and b ,stands for a's reward should be more than b's.

Output

For every case ,print the least money dandelion 's uncle needs to distribute .If it's impossible to fulfill all the works' demands ,print -1.

Sample Input

2 1
1 2
2 2
1 2
2 1

Sample Output

1777
-1
#include <cstdio>
#include <queue>
#define MAX 10000+1
using namespace std;

int n,m;
//n个works(工人)，m个demands(约束条件) 
int cost[MAX],in[MAX];
//cost[i] 表示用在i身上的开销
//in[i] 表示i点的入度 
vector <vector<int> > v;

void toposort(){
    queue <int> q;
    for(int i = 1;i<=n;i++){
        if(in[i]==0)//初始化，将所有入度为0的点入队 
			q.push(i);
	}
	
    int minCost=888;
    while(!q.empty()){//还有点未被处理 
    	int qSize = q.size();//记录该轮有多少个点为入度为0的 
        for(int i = 0;i<qSize;i++){
        	
            int u = q.front(); q.pop();//取出该点并弹出队列 
            cost[u]=minCost;//该点的所需要的花费 
            
			for(int i = 0;i<v[u].size();i++){
                int d = v[u][i];//u-->v[u][i]
                in[d]--; //u[u][i]-- 
                if(in[d] == 0)//在这个过程中，若某点的入度变为0，则入队 
					q.push(d);
            }
        }
        minCost++;
    }
    
}
 
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){//n个工人，m个约束条件 
        //初始化 
		v.clear();//清除v数组 
    	v.resize(n+1); //设置v数组大小 
    	for(int i = 0;i<=n;i++){
        	cost[i]=-1;  
       		in[i]=0;  
    	}
    	
    	int a,b;
    	for(int i = 0;i<m;i++){
    		scanf("%d%d",&a,&b);//a的reword高于b的，即a <-- b
    	    v[b].push_back(a); //将a压入到v[b]当中  b -->a
    	    in[a]++; //a的入度加一 
    	} 
	
		toposort();
		int sum=0;
    	for(int i=1;i<=n;i++){
        	if(cost[i]>0) sum+=cost[i];
        	else{
            	sum=-1;
            	break;
        	}
    	}
   		printf("%d\n",sum);
    }
    return 0;
}