VOCV  ConJunctions
The city of YO is a network of twoway streets and junctions with the following properties:
 There is no more than one street between each pair of junctions.
 Every junction is connected to every other junction either directly via a street or through other junctions by a unique path.
 When a light is placed at a junction, all the streets meeting at this junction are also lit.
A valid lighting is a set of junctions such that if lights were placed at these, all the streets would be lit. An optimal lighting is a valid lighting such that it contains the least number of junctions.
The task is divided into two subtasks:
 Find the number of lights in an optimal lighting.
 Find the total number of such optimal lightings in the city.
Input
 The first line of the input contains a positive integer t <= 20, denoting the number of test cases.
 The description of the test cases follows one after the other.
 Network Description:
 The first line of description of a network consists of a positive integer n <= 100010 denoting the number of junctions in the network.
 Each junction is numbered with a unique integer between 1 and n.
 The following n1 lines contain a pair of integers u v (1 <= u,v <= n) separated by a single space denoting that there is a street between junction u and junction v.
Output
The output must consist of t lines, the k^{th} line corresponding to the k^{th} network; (1 <= k <= t). The k^{th} line must contain two integers separated by a single space. The first integer on the k^{th} line must be the number of junctions in an optimal lighting of network k. The second integer must be N%10007, which is the remainder left by the number of optimal lightings when divided by 10007.
Example
Input:
2
4
1 2
2 3
3 4
3
1 2
1 3
Output:
2 3
1 1
hide comments
thanos_tapras:
20200605 18:43:02
Very nice variation of known problem!


lnxdx:
20191004 15:25:35
AC in shit! 

kmkhan_014:
20180514 22:33:19
understanding the bottom up appproach will help you in solving subtask 2. good luck! 

rahulpadhy:
20170103 20:20:00
Awesome problem.. DFS with DP works nicely :)


Sumit Vohra:
20160213 17:18:01
took some time, dP on tree :) 

xxbloodysantaxx:
20150720 21:21:51
Writing the bottom up for this problem gives you real essence of DP :) 

Ankit Sultana:
20150627 21:43:32
Note: Don't take mod for first integer in output 

paras meena:
20140901 11:45:11
Really Nice Problem ;) 
Added by:  Kashyap KBR 
Date:  20051212 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NEM NICE NODEJS PERL6 SCM qobi ST VB.NET 