#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, a, b, start, col[20];
bool conn[20][20];
vector<int> c[20];
queue<int> g;
int main()
{
    freopen("DATA5.txt", "r", stdin);
    freopen("OUT5.txt", "w", stdout);
    for (int q = 0; q < 5; q++)
    {
        for (int j = 0; j < 20; j++)
        for (int i =0 ; i < c[j].size(); i++)
            c[j].erase(c[j].begin()+i);
        cin >> n;
        for (int i = 0; i < 20; i++)
        {
            for (int j = 0; j < 20; j++)
                conn[i][j] = false;
            col[i] = -1;
        }
        for (int i = 0; i < n; i++)
        {
            cin >> a >> b;
            --a, --b;
            if (i == 0) start = a;
            conn[a][b] = conn[b][a] = true;
        }
        for (int i = 0; i < 20; i++) conn[i][i] = false;
        for (int i = 1; i < 4; i++) c[start].push_back(i);
        col[start] = 0;
//        ans++;
        g.push(start);
        bool fin = true;
        while (!g.empty())
        {
            int curr = g.front(), next = -1;
            g.pop();
            for (int i = 0; i < n; i++)
                if ((curr != i) && (conn[i][curr]) && (col[i] == -1))
                {
                    if (next == -1) next = i;
                    c[i].push_back(col[curr]);
                }
//            cout << next << endl;
            bool poss = false;
            for (int i = 0; i < 4; i++)
            {
                bool good = true;
                for (int j = 0; j < c[next].size(); j++)
                    if (c[next][j] == i)
                    {
                        good = false;
                        break;
                    }
                if (good)
                {
                    poss = true;
                    col[next] = i;
                    break;
                }
            }
            if (!poss)
            {
                cout << 0 << endl;
                fin = false;
                break;
            }
            if (next == -1)
            {
                for (int i = 0; i < n; i++)
                    if (col[i] == -1)
                    {
                        g.push(i);
                        col[i] = 0;
                    }
            }
            else
            {
                g.push(next);
//                cout << next << " " << col[next] << endl;
            }
//            system("PAUSE");
//            cout << "A" << endl;
        }
        if (fin)
        {
            int ans = -1;
            for (int i = 0; i < n; i++)
                ans = max(ans, col[i]);
            cout << ans + 1 << endl;
        }
    }
    return 0;
}