Monique and Paul both enjoy math and programming a lot. A few days ago they decided to compete against each other in many kinds of problem solving competitions. They solved hundreds of problems, but they still have not decided who the winner is, because the current score is surprisingly a draw. Monique gets impatient, and proposed a final game to decide the battle between them. The game is played as follows:
First, Monique constructs a tree with N nodes and binary weights on the edges of the tree. The weights are not known initially, but the structure of the tree is. After that, she writes down a list of Q distinct queries of the form:
\(query(v, u)\) - returns a parity of the sum of values on edges on the path from node v to node u in the tree. Each query has assigned a cost \(c_{v, u}\) denoting the cost of asking that query.
Finally, she gives Paul two days to find the number of subsets S of the set of all queries such that after asking all queries from S, Paul can be sure what values are assigned to all edges of the tree Monique constructed and that the sum of costs of queries in S is the lowest from all such subsets. Since this number can be very large, Paul has to return it modulo \(10^9 + 7\).
The task is to help Paul solve the problem, so he can defeat Monique.
Input format:
In the first line there are two space separated integers N and Q denoting the number of nodes in the tree and the number of all possible queries. In each of the next \(N - 1\) lines there are two space separated integers \(v, u\) denoting that there is an edge between nodes v and u in the tree. In each of the following Q lines there are three space separated integers \(v, u, c_{v, u}\) denoting a single queries \(query(u, v)\), where \(c_{v,u}\) is the cost of asking the query.
Constraints:
\(2 \leq N \leq 75\)
\(1 \leq Q \leq N \cdot (N - 1) / 2\)
\(1 \leq v, u \leq N\)
\(v \neq u\)
\(1 \leq c_{v,u} \leq 10^5\)
all queries in the input are distinct
Output format:
In a single line output a single integer denoting the answer to the problem.
In the sample, the tree Monique created looks like this:
2
|
1
/ \
3 4
She gives 3 queries possible to ask:
- \(query(2, 3)\) with cost 1
- \(query(4, 2)\) with cost 1
- \(query(1, 2)\) with cost 2
The best Paul can do is to ask all available queries with total cost equal to \(1 + 1 + 2 = 4\).
After asking the third query, Paul knows the value assigned to edge \((1, 2)\). After that, if he asks the first query, he can figure out the value assigned to edge \((1, 3)\). Finally, after asking the second query, he can figure out the value assigned to edge \((1, 4)\). It is not possible to figure out values assigned to all edges asking a different set of queries with lower cost. It follows that there is only one subset of all queries with the lowest total cost, such that the queries in this set are sufficient to figure out values assigned to all the edges.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor