#include using namespace std; bool M1; #define task "task" #define bit(x, i) ((x >> i) & 1) // https://trap.jp/post/1224/ #define FOR1(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++) #define FOR2(i, a, b, c) for(int i = (a), _b = (b); i <= _b; i += c) #define FORD1(i, a, b) for(int i = (a), _b = (b); i >= _b; i --) #define FORD2(i, a, b, c) for(int i = (a), _b = (b); i >= _b; i -= c) #define overload4(a, b, c, d, name, ...) name #define FOR(...) overload4(__VA_ARGS__, FOR2, FOR1)(__VA_ARGS__) #define FORD(...) overload4(__VA_ARGS__, FORD2, FORD1)(__VA_ARGS__) #define pb emplace_back #define pf emplace_front #define ins emplace #define mp make_pair #define fi first #define se second #define lb lower_bound #define ub upper_bound #define all(v) v.begin(), v.end() using ll = long long; using pii = pair; using pll = pair; using vi = vector; using vl = vector; // mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); // ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution(l, r)(rd); } const int N = 2e5 + 5; const ll inf = 1e18; const int mod = 1e9 + 7; const int base = 31; int n, dp[N][2]; vector g[N]; void dfs(int u, int p){ dp[u][0] = 1; for(int v : g[u]) if(v != p){ dfs(v, u); dp[u][0] += max(dp[v][1], dp[v][0] - 1); dp[u][1] += max(dp[v][0], dp[v][1]); } } void solve(){ cin>>n; FOR(i, 1, n - 1){ int u, v; cin>>u>>v; g[u].pb(v); g[v].pb(u); } dfs(1, 0); cout<>tc; while(tc --) solve(); cerr << "\nMemory: " << abs(&M2-&M1)/1024.0/1024 << " Mb\n"; cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << " ms\n"; return 0; }