#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

bool a[maxn][maxn],A[maxn];

int n,ans;

void gauss(){

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

        int r=i;

        for(int j=i;j<=n;j++)if(a[j][i]){r=j;break;}

        if(!a[r][i])continue;

        if(r!=i)for(int j=i;j<=n+;j++)swap(a[i][j],a[r][j]);

        for(int j=i+;j<=n;j++)if(a[j][i]){

            for(int k=n+;k>=i;k--){

                a[j][k]^=a[i][k];

            }

        }

    }

}

void dfs(int x,int now){

    if(now>=ans)return;

    if(!x){ans=now;return;}

    if(a[x][x]){

        A[x]=a[x][n+];

        for(int j=x+;j<=n;j++)A[x]^=a[x][j]*A[j];

        dfs(x-,now+A[x]);

    }

    else{

        A[x]=;dfs(x-,now);

        A[x]=;dfs(x-,now+);

    }

}

int main(){

    scanf("%d",&n);

    while(n){

        memset(a,,sizeof(a));

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

            int u,v;

            scanf("%d%d",&u,&v);

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

        }

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

        gauss();

        ans=0x3f3f3f3f;

        dfs(n,);

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

        scanf("%d",&n);

    }

    return ;

}