#include <fstream>
#include <iostream>

using namespace std;

bool color[21][4],map[21][21],looked[21];
int marked[21];

void mark(int i){
    looked[i]=true;
    for(int j=0;j<4;j++){
        if (color[i][j])
        {
            marked[i]=j;
            break;
        }
    }
    for (int j=0;j<21;j++){
        if (map[i][j]) color[j][marked[i]]=false;
    }
    //for (int j=0;j<21;j++){
    //    if (looked[j]==true) mark(j);
    //}
}
int main()
{
    ifstream fin("DATA5.txt");
    ofstream fout("OUT5.txt");
    int times,a,b,biggest;
    for(int t=0;t<5;t++){
    fin>>times;
    biggest=0;
    for (int i=0;i<21;i++){
        marked[i]=4;
        looked[i]=false;
        for (int j=0;j<21;j++){
            map[i][j]=false;
            if (j<4){
                //cout<<i<<" "<<j<<endl;
                color[i][j]=true;
            }
        }
    }
    for (int i=0;i<times;i++){
        fin>>a>>b;
        map[a-1][b-1]=true;
        map[b-1][a-1]=true;
    }
    for(int i=0;i<21;i++){
        if (looked[i]==false) mark(i);
    }
    for(int i=0;i<21;i++){
        if (marked[i]>biggest) biggest=marked[i];
    }
    if (biggest==4) biggest=-1;
    fout<<biggest+1<<endl;
    }
    return 0;
}