#include <bits/stdc++.h>
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse; 
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef long long li;
typedef long double lf;

inline li read(){
	li ans = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		f = (ch == '-') ? -1 : 1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans * f;
} 

li kind, T, n, m;
vector<li> a[100010];

namespace workA{
	li lenscc, belong[100010], used[100010], lendfn, dfn[100010], low[100010], stack[100010], lenstack;
	
	void dfs(li u){
		dfn[u] = low[u] = ++lendfn;
		used[stack[++lenstack] = u] = 1;
		for(li v : a[u]){
			if(!dfn[v]){
				dfs(v);
				low[u] = min(low[u], low[v]);
			} else if(used[v]) low[u] = min(low[u], dfn[v]);
		}
		if(low[u] == dfn[u]){
			lenscc++;
			while(used[u]){
				used[stack[lenstack]] = 0;
				belong[stack[lenstack--]] = lenscc;
			}
		}
	}
	
	li vis[100010], cnt;
	void dfs2(li u){
		//		cout << "u = " << u << " " << vis[u] << endl;
		cnt++;
		vis[u] = 1;
		for(li v : a[u]){
			if(!vis[v]) dfs2(v);
		}
	}
	
	void work(){
		T = read();
		while(T--){
			n = read(), m = read();
			for(li i = 1; i <= n; i++) a[i].clear(), cnt = vis[i] = used[i] = belong[i] = dfn[i] = low[i] = stack[i] = lendfn = lenscc = lenstack = 0;
			//			cout << "?" << endl;
			for(li i = 1; i <= m; i++){
				li u = read(), v = read();
				a[u].push_back(v);
			}
			//			cout << "?" << endl;
			for(li i = 1; i <= n; i++){
				if(!dfn[i]) dfs(i);
			}
			for(li i = 1; i <= n; i++){
				if(belong[i] == lenscc){
					dfs2(i);
					break;
				}
			}
			//			cout << cnt << endl;
			for(li i = 1; i <= n; i++){
				if(belong[i] == lenscc && cnt == n){
					printf("2");
				} else{
					printf("3");
				}
			}
			puts("");
		}
		exit(0);
	}
}

namespace workBC{
	li vis[100010], vis2[100010], cnt;
	vector<li> b[100010];
	li vis3[100010], vis4[100010];
	
//	void dfs(li u){
//		//		cout 
//		vis3[u] = 2;
//		for(li v : a[u]){
//			if(vis3[v] == 2) continue;
//			if(vis3[v] == 1){
//				vis4[v] = 1;
//			}
//		}		
//	}
	
	queue<li> q;
	bool dfs2(li u){
		cnt++;
		vis2[u] = 2;
		q.push(u);
		for(li v : b[u]){
			if(vis2[v] == 2) continue;
			if(vis2[v] == 1) return 0;
			li fl = dfs2(v);
			if(!fl) return 0;
		}
		vis2[u] = 1;
		return 1;
	}
	
	void work(){
		T = read();
		while(T--){
			n = read(), m = read();
			for(li i = 1; i <= n; i++) a[i].clear(), b[i].clear(), vis[i] = vis3[i] = vis4[i] = 0;
			for(li i = 1; i <= m; ++i){
				li u = read(), v = read();
				a[v].push_back(u);
				b[u].push_back(v);
			}
			vis[1] = 1;
//			dfs(1);
			for(li i = 1; i <= n; i++){
				//				if(vis[i] == 1){
				cnt = 0;
				while(!q.empty()) vis2[q.front()] = 0, q.pop();
				if(dfs2(i) && cnt == n){
					printf("1");
				} else{
					printf("3");
				}
				//					printf("1");
				//				}				
				//				else printf("3");
			}
			puts("");
		}
		exit(0);
	}
}

namespace dzd{
	vector<pair<li, li>> a[200010];
	li s, cnt, vis2[200010];
	li vis[200010], ans[200010];
	
	bool dfs2(li u){
		cnt++;
		vis2[u] = 2;
		for(auto t : a[u]){
			li v = t.first;
			if(s >> (t.second - 1) & 1) continue;
			if(vis2[v] == 2) continue;
			if(vis2[v] == 1) return 0;
			li fl = dfs2(v);
			if(!fl) return 0;
		}
		vis2[u] = 1;
		return 1;
	}
	
	void work(){
		T = read();
		while(T--){
			n = read(), m = read();
			for(li i = 1; i <= n; i++){
				a[i].clear();
			}
			for(li i = 1; i <= m; i++){
				li u = read(), v = read();
				a[u].push_back({v, i});
			}
			s = 0;
			for(li i = 1; i <= n; i++){
				for(li j = 0; j <= n; j++) vis2[j] = 0;
				cnt = 0;
				vis[i] = (dfs2(i) && cnt == n);
//				cout << i << " " << cnt << " " << vis[i] << endl;
			}
			for(s = 1; s < (1 << m); s++){
				for(li i = 1; i <= n; i++){
					if(!vis[i]){
						for(li j = 1; j <= n; j++) vis2[j] = 0;
						cnt = 0;
						if(dfs2(i)){
							if(cnt == n){
								vis[i] = 2;
							}
						}
					}
				}
			}
			for(li i = 1; i <= n; i++){
				if(!vis[i]) vis[i] = 3;
				printf("%lld", vis[i]);
			}
			puts("");
		}
		exit(0);
	}
}

int main(){
//		freopen("wonderful.ans", "r", stdin);
//		freopen("www.ww", "w", stdout);
	kind = read();
	if(kind == 1) dzd::work();
	if(kind == 2 || kind == 7) workA::work();
	workBC::work();
	return 0;
}