#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<pair<int,int>>g[1005];

int dj[3005],dist[1005];

void dfs(int x,int la){

	for(auto pi:g[x]){

		int cu=pi.first,c2=pi.second;

		if(cu==la)continue;

		dist[cu]=dist[x]^dj[c2];

		dfs(cu,x);

	}

}

int af[1005];

void dfss(int x,int la){

	for(auto pi:g[x]){

		int cu=pi.first;

		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;

}

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(12345678);

	while(TT--){

		vector<int>ok(m),p(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.begin(),p.end(),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,i);

				g[v].emplace_back(u,i);

			}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){

				dj[i]=s[t][i];

			}

			dfs(0,-1);

			for(int i=0;i<m;++i)if(ok[i]){

				int u=x[i][2],v=x[i][3];

				he+=dj[i]^dist[u]^dist[v];++gs;

			}

		}

	}

	if(1.0*he/gs<0.474)return 2;

	return 1;

}