VOCV - Con-Junctions


The city of Y-O is a network of two-way streets and junctions with the following properties:

  1. There is no more than one street between each pair of junctions.
  2. Every junction is connected to every other junction either directly via a street or through other junctions by a unique path.
  3. 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:

  1. Find the number of lights in an optimal lighting.
  2. 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 n-1 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 kth line corresponding to the kth network; (1 <= k <= t). The kth line must contain two integers separated by a single space. The first integer on the kth 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: 2020-06-05 18:43:02

Very nice variation of known problem!

Hint: It is based on the Vertex Cover problem (dp on tree).

lnxdx: 2019-10-04 15:25:35

AC in shit!

kmkhan_014: 2018-05-14 22:33:19

understanding the bottom up appproach will help you in solving subtask 2. good luck!

rahulpadhy: 2017-01-03 20:20:00

Awesome problem.. DFS with DP works nicely :)

Last edit: 2017-01-03 20:20:22
Sumit Vohra: 2016-02-13 17:18:01

took some time, dP on tree :)

xxbloodysantaxx: 2015-07-20 21:21:51

Writing the bottom up for this problem gives you real essence of DP :)

Ankit Sultana: 2015-06-27 21:43:32

Note: Don't take mod for first integer in output

paras meena: 2014-09-01 11:45:11

Really Nice Problem ;)


Added by:Kashyap KBR
Date:2005-12-12
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