CODESPTE  Bytelandian Tours
The country of Byteland contains of N cities and N  1 bidirectional roads between them such that there a path between any two cities. The cities are numbered 0,...,N  1. The people were very unhappy about the time it took to commute, especially salesmen who had to go about every city selling goods. So it was decided that new roads would be built. A new road was built between every two cities which could be reached from each other by travelling on exactly two old roads.
Now a salesman situated in city 0, just like any other typical salesman, has to visit all cities exactly once and return back to city 0 in the end. In how many ways can he do this?
Input:
The first line contains the number of test cases T. T test cases follow. The first line contains N, the number of cities in Byteland. The following N  1 lines contain the description of the roads. The ith line contains two integers a_i and b_i, meaning that there was originally a road connecting cities with numbers a_i and b_i.
Output:
Output T lines, one corresponding to each test case containing the required answer for that test case. Since the answers can be huge, output them modulo 1000000007.
Constraints:
1 <= T <= 20
1 <= N <= 10000
0 <= a_i,b_i < N
Sample Input:
2
3
0 1
1 2
5
0 1
1 2
2 3
2 4
Sample Output:
2
4
Explanation: For the first case, a new road was build between cities 0 and 2. Now, the salesman has two tour possibilities: 0120 or 0210.
hide comments
lance_haoh:
20170711 11:46:06
I got AC for the exact same problem at HackerRank: https://www.hackerrank.com/challenges/bytelandiantours However, when I submitted the same solution here, I got WA. Problem author, could you please check your test data? 

apia:
20120314 03:31:51
I submited the standard program.But it got WA too.Is there anything wrong with the data? Last edit: 20120314 03:41:50 
Added by:  Varun Jalan 
Date:  20111018 
Time limit:  0.358s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem used for CodeSprint  InterviewStreet Contest 