In a directed connected graph G, there are N nodes and M edges. Among the M edges, for arbitrary given node k (we named the N nodes 1, 2, . . . , N), if there are s edges point to it, we call the node k with a in-degree s, if there are t edges leads from it, we call the node k with a out-degree t. For the given graph G, we define the spanning tree as follows:
- The tree contains N nodes and N-1 edges in G;
- The N nodes are connected.
For the above definition of the spanning tree, if there is a node v meets that, the in-degree of node v is 0, and the in-degree of all the remaining nodes is 1, we call this kind of tree as outward tree roots with v. Now the given task is following:
In arbitrary given connected graph G with N nodes and M edges, can you tell me how many different kinds of trees there are in G meet the following condition?
- Maybe the tree is a outward tree roots with v, and also maybe it\'s only a spanning tree;
- The tree must contains the given h edges, you should assume the h edged belong to G;
You may assume that there is no same direction edge between any two nodes.
2 4 5 0 1 2 1 4 4 2 4 3 3 2 0 4 6 1 1 2 1 4 1 3 2 4 4 3 2 3 1 4 3
Case 1: 8 Case 2: 2