#include<bits/stdc++.h>

using namespace std;

const int Maxlen = , N = ;

int n, ans;

int a[N][N], mark[N], val[N];

namespace IO

{

    char buf[Maxlen], *C = buf;

    int Len;

    inline void read_in()

    {

        Len = fread(C, , Maxlen, stdin);

        buf[Len] = '\0';

    }

    inline void fread(int &x)

    {

        x = ;

        int f = ;

        while (*C < '' || '' < *C) { if(*C == '-') f = -; ++C; }

        while ('' <= *C && *C <= '') x = (x << ) + (x << ) + *C - '', ++C;

        x *= f;

    }

    inline void read(int &x)

    {

        x = ;

        int f = ; char c = getchar();

        while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

        while(c >= '' && c <= '') { x = (x << ) + (x << ) + c - ''; c = getchar(); }

        x *= f;

    }

} using namespace IO;

void dfs(int d, int tot)

{

    if(tot >= ans) return;

    if(d == )

    {

        ans = min(ans, tot);

        return;

    }

    if(mark[d])

    {

        int x = a[d][n + ];

        for(int i = ; i <= n; ++i) if(!mark[i] && a[d][i]) x ^= val[i];

        dfs(d - , tot + x);

    }

    else

    {

        val[d] = ;

        dfs(d - , tot);

        val[d] = ;

        dfs(d - , tot + );

    }

}

void gauss()

{

    ans = n;

    for(int now = ; now <= n; ++now)

    {

        int pos = now;

        while(!a[pos][now] && pos <= n) ++pos;

        if(pos == n + ) continue;

        swap(a[pos], a[now]);

        for(int i = ; i <= n; ++i) if(a[i][now] && i != now)

            for(int j = ; j <= n + ; ++j) a[i][j] ^= a[now][j];

        mark[now] = ;

    }

    dfs(n, );

    printf("%d\n", ans);

}

int main()

{

    while()

    {

        read(n);

        if(n == ) break;

        memset(val, , sizeof(val));

        memset(a, , sizeof(a));

        memset(mark, , sizeof(mark));

        for(int i = ; i <= n; ++i)

        {

            a[i][i] = ;

            a[i][n + ] = ;

        }

        for(int i = ; i < n; ++i)

        {

            int u, v;

            read(u);

            read(v);

            a[u][v] = a[v][u] = ;

        }

        gauss();

    }

    return ;

}