Strongly Connected Components Extraction

Lulu loves strongly connected components. In this problem, you are given a directed graph G constructed as follows: you are provided with an undirected tree T with n nodes numbered from 1 to n and m instructions. Initially, the graph G has n nodes (numbered 1 to n) and no edges. For each instruction (a, b, c), for every node x in the tree T such that the shortest path distance between b and x (in T) is at most c (i.e. \(d_T(b,x) \le c\)), add a directed edge from a to x in G.

Your task is to compute the strongly connected components (SCCs) of the directed graph G. Two nodes u and v are in the same strongly connected component if each is reachable from the other.

Once you have computed all the SCCs, output the total number of components in the first line. Then, for each component, output a single line with the nodes in that component listed in increasing order. The components should be printed in the order of their smallest node (i.e. the component with the smallest minimum node comes first).

inputFormat

The input is given as follows:

 n m
 (n-1 lines follow, each containing two integers u and v representing an edge in the tree T)
 m
 (m lines follow, each containing three integers a, b, c representing an instruction)

Here, n is the number of nodes and m is the number of instructions. The tree T is undirected and connected.

outputFormat

Output the number of strongly connected components in the first line. Then, output each strongly connected component in one line. For each component, list its nodes in increasing order, and print the components sorted by their smallest node.

sample

3 1
1 2
2 3
1 2 1

3
1
2
3