#include "prg.h"
#include<bits/stdc++.h>
using namespace std;
int fa[1005];
int findfather(int x){
	return x==fa[x]?x:fa[x]=findfather(fa[x]);
}
vector<int>g[1005];
int dj[1005];
int af[1005],p[3005];
void dfss(int x,int la){
	for(auto cu:g[x]){
		if(cu==la)continue;
		af[cu]=x;
		dfss(cu,x);
	}
}
inline int suan(int u,int v){
	if(af[u]==v||af[v]==u)return 1;
	if(af[af[u]]==v||af[af[v]]==u||af[u]==af[v])return 2;
	if(af[af[af[u]]]==v||af[af[af[v]]]==u||af[u]==af[af[v]]||af[af[u]]==af[v])return 3;
	return 4;
}
inline int dis(int u,int v){
	if(af[u]==v)return dj[u];
	if(af[v]==u)return dj[v];
	if(af[af[u]]==v)return dj[u]^dj[af[u]];
	if(af[af[v]]==u)return dj[v]^dj[af[v]];
	if(af[u]==af[v])return dj[u]^dj[v];
	if(af[af[af[u]]]==v)return dj[u]^dj[af[u]]^dj[af[af[u]]];
	if(af[af[af[v]]]==u)return dj[v]^dj[af[v]]^dj[af[af[v]]];
	if(af[u]==af[af[v]])return dj[u]^dj[v]^dj[af[v]];
	return dj[v]^dj[u]^dj[af[u]];
}
int solve(int n,int m,int k,vector<int>op,array<vector<int>,3000>x,int c,array<array<int,3000>,25>s){
	if(k==2){
		int a1=0,a2=0;
		for(int i=0;i<c;++i){
			int h=0;
			for(int j=0;j<m;++j){
				h+=s[i][j];
			}
			if(h>=(m/4+m/2)/2&&h<=(m*3/4+m/2)/2)++a1;
			else ++a2;
		}
		return (a2<=1?1:2);
	}
	if(op[k-2]!=2){
		int a1=0,a2=0;
		for(int i=0;i<c;++i){
			int h=0;
			for(int j=0;j<m;++j){
				h+=s[i][j];
			}
			if(h>=m/2-m/16&&h<=m/2+m/16)++a1;
			else ++a2;
		}
		return (a2<=1?1:2);
	}
	if(op[k-3]!=2){
		vector<vector<int>>gs(n);
		for(int i=0;i<m;++i){
			gs[x[i][k-1]].emplace_back(i);
		}
		int mn=0,ms=0;
		for(int i=0;i<n;++i)if((signed)gs[i].size()>=2){
			int t=gs[i].size(),kn=0;
			for(int j=0;j<c;++j){
				int h=0;
				for(auto k:gs[i]){
					h+=s[j][k];
				}
				if(h==0||h==t)++kn;
			}
			mn+=kn;++ms;
		}
		if(1.0*mn/ms>6.7)return 2;
		return 1;
	}
	if(op[0]==1){
		for(int i=0;i<c;++i){
			for(int j=0;j<m;++j){
				s[i][j]^=1;
			}
		}
	}
	int he=0,gs=0;
	int TT=17;
	mt19937 mt(20091201);
	while(TT--){
		vector<int>ok(m),ko(m);
		for(int i=0;i<n;++i)fa[i]=i,g[i].clear();
		for(int i=0;i<m;++i)p[i]=i;
		shuffle(p,p+m,mt);
		for(int ii=0;ii<m;++ii){
			int i=p[ii];
			int u=x[i][2],v=x[i][3];
			int fu=findfather(u),fv=findfather(v);
			if(fu!=fv){
				fa[fu]=fv;
				g[u].emplace_back(v);
				g[v].emplace_back(u);
				ko[i]=1;
			}else{
				ok[i]=1;
			}
		}
		af[0]=af[n]=n;dfss(0,-1);
		for(int i=0;i<m;++i)if(ok[i]){
			int ds=suan(x[i][2],x[i][3]);
			if(ds>3)ok[i]=0;
		}
		for(int t=0;t<c;++t){
			for(int i=0;i<m;++i)if(ko[i]){
				int u=x[i][2],v=x[i][3];
				if(af[u]==v)dj[u]=s[t][i];
				else dj[v]=s[t][i];
			}
			for(int i=0;i<m;++i)if(ok[i]){
				int u=x[i][2],v=x[i][3];
				he+=s[t][i]^dis(u,v);++gs;
			}
		}
	}
	if(1.0*he/gs<0.473)return 2;
	return 1;
}