#include <fstream>
#include <iostream>
#include<vector>
using namespace std;

typedef struct {
	vector<int> edges[21];
	int ne, nv;
}graph;

int color[21];
int nc = 0;

bool colorFrom(graph* g, int v) {
    /*cout << v << endl;
    	for (int i=1; i<=4; i++) {
			cout << i << ":";
            for (int j=0; j<g->edges[i].size(); j++)
                cout << " "  << g->edges[i][j];
            cout << endl;
		}*/
    
	bool done = false;
    for (int c = 1; c<=4; c++) {
		color[v] = c;

		//check if this color can be used
		bool possible = true;
		for (int i=0; i<g->edges[v].size() && possible; i++) {
            //cout << i << " " << g->edges[v][i]; system("pause");
            if (g->edges[v][i] == v) continue;
			if (color[g->edges[v][i]] == color[v]) possible = false;
        }
		if (!possible) continue;
		
		//color its neighbours
		for (int i=0; i<g->edges[v].size() && possible; i++) {
            //cout << g->edges[v][i] << endl;system("pause");
			if (g->edges[v][i] == v) continue;
			if ( color[g->edges[v][i]] == -1) {
				if (!colorFrom(g, g->edges[v][i]))
					possible = false;
            }
		}
		if (possible) {
            done = true;
            break;
        }
	}
	
	if (done) {
		nc = max(nc, color[v]);
		return true;
	}
	else {
		color[v] = -1;
		return false;
	}
}

int main() {
	ifstream fin("data5.txt");
	ofstream fout("out5.txt");
	
	for (int ncases = 0; ncases<5;  ncases++) {
		graph* g = new graph;
		fin >> g->ne; 
		for (int i=0; i<g->ne; i++) {
			int a, b;
			fin >> a >> b;
			g->edges[a].push_back(b);
			g->edges[b].push_back(a);
		}
		
		/*for (int i=1; i<=4; i++) {
			cout << i << ":";
            for (int j=0; j<g->edges[i].size(); j++)
                cout << " "  << g->edges[i][j];
            cout << endl;
		}*/
		
		for (int v=1; v<=20; v++) color[v] = -1;
		
		bool possible = true;
		for (int v=1; v<=20; v++) {
			if (g->edges[v].size() == 0) continue;
			if (color[v] == -1) possible = colorFrom(g, v);
			if (!possible) fout << 0 << endl; break;
		}
		
		if (possible) {
            //for (int i=1; i<=4; i++) fout << i << " " << color[i] << endl;
			fout << nc << endl;
				
			//print out number of colors used
		}
	}
	return 0;
}