///*
// * map06.cpp
// *
// *  Created on: May 15, 2024
// *      Author: 28032
// */
//// 1.先将ways数组全部初始化成0
//// 2.用DFS从1开始遍历图
//// ways[v] == 0时，直接标记，并以此再发起DFS
//// ways[v] == 1时，说明在这一路的DFS中访问了一个结点两次，有环
//// ways[v] == 2时，说明前面的几路DFS中曾经访问过该节点，有多路
//// 3.一次DFS还不行，many和cycle的标记还在上游，没有传到下游去
//// 所以这次DFS目的是将该节点的标记传给它的下一结点
//#include <iostream>
//#include <set>
//#include<string.h>
//
//using namespace std;
//int T,n,m;
//set<int> *g;
//bool *many,*cycle,*vis;
//int *ways;
//void dfs1(int v)
//{
//	for(int p : g[v])
//	{
//		switch(ways[p])
//		{
//		case 0:
//			ways[p] = 1;
//			dfs1(p);
//			break;
//		case 1:
//			cycle[p] = true;
//			break;
//		case 2:
//			many[p] = true;
//			break;
//		}
//	}
//	ways[v] = 2;
//}
//
//void dfs2(int v)
//{
//	vis[v] = true;
//	if(many[v])
//		for(int p : g[v])
//			many[p] = true;
//	if(cycle[v])
//		for(int p : g[v])
//			cycle[p] = true;
//
//	for(int p : g[v])
//		if(!vis[p])	dfs2(p);
//}
//
//void getRes(void)
//{
//	for(int i = 1;i <= n;i++)
//	{
//		if(ways[i] == 0)
//			continue;
//		ways[i] = 1;
//		if(many[i] && !cycle[i])
//			ways[i] = 2;
//		else if(cycle[i])
//			ways[i] = -1;
//	}
//}
//
//int main()
//{
//	cin>>T;
//
//	while(T--)
//	{
//		cin>>n>>m;
//		g = new set<int>[n+1];
//		many = new bool[n+1];
//		cycle = new bool[n+1];
//		vis = new bool[n+10];
//		ways = new int[n+1];
//		for(int i = 1;i <=n;i++)
//		{
//			many[i] = false;
//			cycle[i] = false;
//			vis[i] = false;
//			ways[i] = 0;
//		}
//
//		for(int i = 1;i <= m;i++)
//		{
//			int a,b;
//			cin>>a>>b;
//			g[a].insert(b);
//		}
//
//		dfs1(1);
//		dfs2(1);
//		getRes();
//
//		for(int i = 1;i <=n;i++)
//			cout<<ways[i]<<" ";
//		cout<<endl;
//
//		delete[] ways;
//		delete[] cycle;
//		delete[] many;
//		delete[] g;
//	}
//
//
//
//	return 0;
//}
//
//
//