1612: Tree

给一棵树，你可以匹配有边相连的两个点，问你这棵树的最大匹配是多少，并且计算出有多少种最大匹配。

Once upon a time in a kingdom far far away, the royal treasury started getting emptier and emptier. The king decided to change the situation and he invented a new system of cooperation with in the office of the royal treasurer. The clerks of the office are supposed to form pairs (in order to avoid being bribed) in such away that each pair is formed by a clerk and his/her direct subordinate. Your task is to compute, given the structure of the office of the treasurer, the maximum number of pairs that can be formed this way and in how many different ways this is possible.

The office of the treasurer is led by George Skinflint. Each clerk has zero, one or more subordinates and is a subordinate of a single clerk (except for George Skinflint who is responsible only to the king himself). The number of clerks does not exceed 1000. Your task is to compute the maximum number of pairs that can be formed by clerks in such a way that every pair is formed by a clerk and his/her direct subordinate. In addition, you should also compute the number of ways such pairs can be formed. Note that some clerks need not be contained in a pair.

第一行一个数N,表示有多少个结点。
    接下来N行，每行第一个数表示要描述的那个结点.然后一个数m，表示这个结点有m个儿子，接下来m个数，表示它的m个儿子的编号。

The first line of each testcase contains a single number N that represents the number of clerks 1 <= N <= 1000. The clerks are assigned unique ID numbers from the range between 1 and N. The ID number of the treasurer (Skinflint) is 1. Each of the following N lines corresponds to one of the clerks: it contains his/her ID number, the number K of his/her subordinates, 0 <= K <= 999, and the ID numbers of his/her K subordinates separated by single spaces. You can assume that the line corresponding to a clerk never appears before the line corresponding to his/her supervisor.

输出两行，第一行输出最大匹配数，第二行输出最大匹配方案数。

The output for each testcase should consist of two lines. The first line of the output should contain a single number that represents the maximum number M of pairs that the clerks can form. The second line should contain the number of different ways in which the clerks can form M pairs obeying the rules given by the king.

7
1 3 2 4 7
2 1 3
4 1 6
3 0
7 1 5
5 0
6 0

3
4