21 Days Trainging // Day 5

0. forest

Solution

Notice that

1. Each operation (u, v) will make the node u a leaf node
2. You cannot make u or v a leaf node, or this operation will not change the shape of the tree.

Code :

#include 
using namespace std;

int main() {
    int T;cin >> T;
    for (int _T=0;_T> N;
        map deg;
        for (int i=0;i> u >> v;u--;v--;
            if (deg.find(u)==deg.end()) deg[u]=0;
            if (deg.find(v)==deg.end()) deg[v]=0;
            deg[u]++, deg[v]++;
        }
        if (N==2) cout << "villager" << endl;
        else {
            int count=0;
            for (int i=0;i<N;i++) count += (deg[i]==1?0:1);
            cout << (count%2?"villager":"wizard") << endl;
        }
    }
    return 0;
}

Special Conditions :
For N=2, directly output "villager", since hte wizard cannot operate at first. (Line 16)