PYRA

#include <cstdio>
#include <vector>
#include <deque>
using namespace std;

vector< deque< int > > theGraph;
int totalSize;
int visited[10000];

int bfs( int node ){
  //printf("Visiting node %d...\n",node);
  int result = 1;
  for( deque<int>::iterator it = theGraph[ node ].begin(); it != theGraph[ node ].end(); it++ ){
    if( visited[*it] ) continue;
    visited[*it] = 1;
    result += bfs( *it );
    result++;
  }
  totalSize += result;
  //printf("Length of node %d is %d, total size is %d\n",node,result,totalSize);
  return result;
}

int main( int argc, char* argv[] ){
  int t,n,i,j;
  theGraph.resize( 10000 );
  scanf("%d",&t);
  while( t-- ){
    scanf("%d",&n);
    for( int k = 0; k < n; k++ ) { theGraph[ k ].clear(); }
    totalSize = 0;
    visited[0] = 1;
    for( int k = 1; k < n; k++ ){
      visited[k] = 0;
      scanf("%d %d",&i,&j);
      theGraph[ i ].push_back( j );
      theGraph[ j ].push_back( i );
    }
    bfs( 0 );
    printf("%d\n", totalSize );
  }
  return 0;
}