C++ :

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<math.h>

using namespace std;

#define INF 0x3f3f3f3f

int n,m;
int a[100010],b[100010];
vector<int> edge[10010];
int inD[10010];

bool check(int x){
	for(int i = 1;i <= n;++i){
		edge[i].clear();
		inD[i] = 0;
	}
	for(int i = 1;i <= x;++i){
		edge[a[i]].push_back(b[i]);
		++inD[b[i]];
	}
	queue<int> q;
	for(int i = 1;i <= n;++i)
		if(inD[i] == 0)
			q.push(i);
	int cnt = 0;
	while(!q.empty()){
		int now = q.front();
		q.pop();
		++cnt;
		for(int i = 0;i < edge[now].size();++i){
			--inD[edge[now][i]];
			if(inD[edge[now][i]] == 0)
				q.push(edge[now][i]);
		}
	}
	return cnt == n;
}

int main(){
	int T;
	scanf("%d",&T);
	for(int caseT = 1;caseT <= T;++caseT){
		scanf("%d%d",&n,&m);
		for(int i = 1;i <= m;++i)
			scanf("%d%d",&a[i],&b[i]);
		int ans = -1;
		int left = 1,right = m;
		while(left <= right){
			int mid = (left + right) >> 1;
			if(check(mid)){
				ans = max(ans,mid);
				left = mid + 1;
			}else{
				right = mid - 1;
			}
		}
		printf("Case %d: %d\n",caseT,ans);
	}
	return 0;
}