Code: Select all
#include <vector>
#include <stack>
#include <iostream>
#include <cstdio>
using namespace std;
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define input ({int _t; scanf("%d", &_t); _t;})
typedef vector<int> vint;
typedef struct _nodo{
vint adj;
int par;
int ind;
bool mark;
_nodo(){par=-1;mark = false;}
} nodo;
#define p(a) cout << a << endl
int main()
{
int T = input;
forn(TT,T)
{
int N = input;
vector<nodo> tree = vector<nodo>(N);
int a,b;
forn(i,N) tree[i].ind = i;
forn(i,N-1)
{
a = input;
b = input;
tree[a].adj.push_back(b);
tree[b].par=a;
}
vint raiz;
forn(i,N)
if(tree[i].par == -1){
raiz.push_back(i);
//~ p("raiz "<<i);
}
int res = 0;
stack<nodo> dfs;
forn(i,raiz.size())
dfs.push(tree[raiz[i]]);
while(!dfs.empty())
{
nodo top = dfs.top();
dfs.pop();
if(top.mark){res++;continue;}
if(top.adj.size())
{
forn(i,top.adj.size())
//~ if(!tree[top.adj[i]].mark)
dfs.push(tree[top.adj[i]]);
}else{
res++;
}
tree[top.ind].mark = true;
}
p("Case "<<TT+1<<": "<<res);
}
}