Ancestor Edge Query

Given a tree with \(n\) nodes and \(n-1\) edges numbered from \(1\) to \(n-1\), where the \(i\)-th edge has a weight \(b_i\) and the tree is rooted at node \(1\). For an edge, we define its deeper vertex as the vertex with the larger depth (according to a DFS starting at the root). For two distinct edges \(x\) and \(y\), we say that \(x\) is an ancestor of \(y\) if and only if the deeper vertex of edge \(x\) is an ancestor (in the tree) of the deeper vertex of edge \(y\), i.e. if \(\text{tin}(d_x) \le \text{tin}(d_y)\) and \(\text{tout}(d_y) \le \text{tout}(d_x)\), where \(d_x\) and \(d_y\) are the deeper vertices for edges \(x\) and \(y\) respectively.

There are \(m\) queries. In the \(i\)-th query, you are given \(t_i\) (possibly repeated) nodes. Consider the union (set) of edges lying on the simple paths between every pair of these nodes (i.e. the edges of the minimal subtree connecting these nodes). Your task is to count the number of unordered pairs of distinct edges \(\{x,y\}\) from this set such that edge \(x\) is an ancestor of edge \(y\) and \(b_x < b_y\). Note that since the pair is unordered, the condition uniquely determines the order (the one higher in the tree is \(x\) and the lower one is \(y\)).

Input is guaranteed to be such that a simple solution with moderate constraints will pass.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of nodes in the tree and the number of queries respectively.

Then \(n-1\) lines follow, each containing three integers \(u\), \(v\) and \(b\) indicating there is an edge between nodes \(u\) and \(v\) with weight \(b\). The edges are numbered in the order of input from \(1\) to \(n-1\>.

After that, there are \(m\) queries. Each query starts with an integer \(t\) (the number of nodes in the query), followed by \(t\) integers representing the nodes. (Note that the nodes in a query may repeat.)

outputFormat

For each query, output a single line containing the number of valid unordered pairs of edges \(\{x,y\}\) from the union of edges on all simple paths between the given nodes such that edge \(x\) is an ancestor of edge \(y\) and \(b_x < b_y\).

sample

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

0
0