对于每个灯，我们用一个变量表示其决策，x=0表示不选，x=1表示选。因为每个灯最后必须都亮，所以每个等都对应一个异或方程。
解这个异或方程组，有几种情况：
1、存在唯一解（得到的上三角系数矩阵的主对角线上的元素全部为1）
2、无解（存在某行系数全为0，但等式右边不为0）
3、存在v个自由元（即主对角线上有v个0，我们枚举每个自由元的取值，有2种情况）
我们统计所有合法解的最小的值作为答案。
/**************************************************************
Problem: 2466
User: idy002
Language: C++
Result: Accepted
Time:16 ms
Memory:1352 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <iostream>
#define N 100
#define oo 0x3f3f3f3f
using namespace std; int n, ans;
int head[N], dest[N<<], next[N<<], etot;
int aa[N][N+], bb[N][N+], cc[N];
int stk[N], top; void init() {
memset( head, , sizeof(head) );
etot = ;
top = ;
ans = oo;
}
void adde( int u, int v ) {
etot++;
next[etot] = head[u];
dest[etot] = v;
head[u] = etot;
}
void print() {
for( int i=; i<n; i++ ) {
for( int j=; j<=n; j++ )
printf( "%d ", aa[i][j] );
printf( "\n" );
}
printf( "\n" );
}
void gauss() {
for( int i=; i<n; i++ ) {
for( int j=i; j<n; j++ ) {
if( aa[j][i]== ) {
for( int k=i; k<=n; k++ )
swap( aa[i][k], aa[j][k] );
break;
}
}
if( aa[i][i]== ) {
for( int j=i+; j<n; j++ ) {
if( aa[j][i]== ) {
for( int k=i; k<=n; k++ )
aa[j][k] ^= aa[i][k];
}
}
} else {
stk[top++] = i;
}
// print();
}
}
int calc() {
memcpy( bb, aa, sizeof(aa) );
int rt = ;
for( int i=n-; i>=; i-- ) {
bool a=bb[i][i], b=bb[i][n];
if( a ) {
if( b ) {
rt++;
for( int j=i-; j>=; j-- )
bb[j][n] ^= bb[j][i];
} else {
// do nothing
}
} else {
if( b ) {
return oo;
} else {
if( cc[i] ) {
rt++;
for( int j=i-; j>=; j-- )
bb[j][n] ^= bb[j][i];
}
}
}
}
return rt;
}
void dfs( int i ) {
if( i==top ) {
int tans = calc();
if( ans>tans ) ans=tans;
return;
}
cc[stk[i]]=;
dfs(i+);
cc[stk[i]]=;
dfs(i+);
}
int main() {
while( scanf("%d",&n)== && n!= ) {
init();
for( int t=,u,v; t<n; t++ ) {
scanf( "%d%d", &u, &v );
u--, v--;
adde(u,v);
adde(v,u);
}
memset( aa, , sizeof(aa) );
for( int u=; u<n; u++ ) {
aa[u][u] = ;
for( int t=head[u]; t; t=next[t] ) {
int v=dest[t];
aa[v][u] = ;
}
}
for( int v=; v<n; v++ )
aa[v][n] = ;
gauss();
dfs();
printf( "%d\n", ans );
}
}