PRETTYTREE

Problem

Let T be a rooted tree, not necessarily binary. We denote the root of T as ~root(T)~ and the number of nodes as ~size(T)~. We say that T is beautiful if:

• it consists of a single node, or
• it can be formed by starting with two other beautiful trees ~T_1~ and ~T_2~ with ~size(T_1) \ge size(T_2)~ and adding an edge such that the node ~root(T_1)~ becomes the parent of the node ~root(T_2)~.

Thus, a beautiful tree of size ~N~ can be constructed in the following way. We start with ~N~ individual nodes, which by definition are beautiful trees. We repeat the following step ~N-1~ times: we choose two different beautiful trees ~T_1~ and ~T_2~ from those we have, such that ~size(T_1) \ge size(T_2)~, add an edge so that the node ~root(T_1)~ becomes the parent of the node ~root(T_2)~, and thus create a new beautiful tree.

This problem has two versions. In the first version, we are given a rooted tree and asked to determine if it is beautiful or not. In the second version, we are given a rooted tree and asked to count the number of different ways it can be constructed according to the described process (i.e., the number of different sequences in which the edges can be added). If the tree is not beautiful, it obviously cannot be constructed in any way, and thus the answer must be ~0~. The second version of the problem is a generalization of the first.

Input:

The first line of the input will contain two positive integers, ~T~ and ~V~: the number of queries in this file and the version of the problem (~V=1~ for the first version and ~V=2~ for the second).

Following this are ~T~ queries, each of which has the following format: The first line of the query contains a positive integer ~N~: the number of nodes in the tree. The next ~N-1~ lines describe the edges of the tree: each line contains two positive integers ~u~ and ~p~, indicating that node ~u~ has node ~p~ as its parent. We consider the nodes of the tree to be numbered from ~1~ to ~N~.

Output:

The output should contain ~T~ lines, one for each query. Each line should contain the answer to the respective version of the problem.

For the first version ~(V=1)~, the answer should be ~1~ if the tree of the corresponding query is beautiful, otherwise ~0~.

For the second version (~V=2~), the answer should be the number of different ways the tree of the corresponding query can be constructed according to the described procedure. Because this number can be very large, you are required to find its remainder (modulo) when divided by ~10^9+7~.

Constraints

• ~1 \le T \le 5~
• ~1 \le V \le 2~
• ~1 \le N \le 100.000~
• Time Limit: ~1~ sec.
• Memory Limit: ~64~ MB.

Examples of Input - Output:

1st

Input:

2 1
5
2 1
3 1
4 3
5 3
2
1 2

Output:

0
1

Explanation of the first example:

In the first example, ~T=2~, ~V=1~, so we have the first version of the problem and we need to determine if the two given trees are beautiful or not. The first tree cannot be constructed using the above process, therefore it is not beautiful. On the other hand, the second tree is beautiful - it can be constructed simply by making node ~2~ the parent of node ~1~.

2nd

Input:

3 2
4
2 1
3 1
4 3
2
1 2
5
2 1
3 1
4 3
5 3

Output:

2
1
0

Explanation of the second example:

In the second example, ~T=3~ and ~V=2~, indicating the second version of the problem. We need to find out how many different ways the given trees can be formed. The first tree provided is beautiful and can be constructed in two different ways by adding its edges in the following sequences:

• ~4-3~, ~2-1~, ~3-1~
• ~2-1~, ~4-3~, ~3-1~

The second tree in the second example can be formed in only one way, while the third tree is not beautiful and cannot be formed in any way.

Notes

• For test cases with a total value of ~10%~, it will be ~V=1~ and ~1 \le N \le 11~
• For test cases with a total value of ~20%~, it will be ~V=1~ and ~1 \le N \le 21~
• For test cases with a total value of ~35%~, it will be ~V=1~ and ~1 \le N \le 100.000~
• For test cases with a total value of ~15%~, it will be ~V=2~ and ~1 \le N \le 11~. Each node of any tree will have at most ~9~ children.
• For test cases with a total value of ~30%~, it will be ~V=2~ and ~1 \le N \le 21~. Each node of any tree will have at most ~9~ children.
• For test cases with a total value of ~45%~, it will be ~V=2~ and ~1 \le N \le 100~. Each node of any tree will have at most ~9~ children.
• For test cases with a total value of ~65%~, it will be ~V=2~ and ~1 \le N \le 200~. Each node of any tree will have at most ~17~ children.