UFO (Unidentified Flying Object) is spotted in Treeland! This accident has caused many ruckuses among the Treelanders, and many reports have been made to the TreeSDF (Treeland Self Defence Force), the Treeland's police. As you might have suspected from the name, Treeland can be represented as a tree structure. It has N nodes and connected by N-1 undirected edges such that from one node you can visit any other nodes via one or more edges. A node is said to have a distance of d to some other node if and only if both nodes are connected by exactly d edges. By definition, a node has a distance of 0 (zero) to itself.
The incoming reports are in the format of (x, d) which translate to "the UFO was spotted at a node which distance from node x is d". Note that d is not necessarily 0 as the Treelander who made the report may have witness the UFO from a distance.
Unfortunately, each reports may not be precise enough (there may be several nodes satisfying (x, d)) and sometimes wrong (the UFO is not in any node satisfying (x, d)). This issue confuses TreeSDF. As this is a matter of national security (we don't know what the alien's intention), TreeSDF needs to react fast! Help them to find the most probable incident node in which the UFO was spotted. The most probable incident node is the node in Treeland which have the most number of support from the reports, i.e. the report which corresponds to the node. To show the correctness of your work, you only need to output the number of supports for the most probable incident node.
For example, let there be 10 nodes (numbered from 1 to 10) and 5 reports: (3, 2), (4, 2), (8, 3), (9, 4), and (10, 3).
In this example, the most probable incident node is node 5 with 3 supports: (3, 2), (4, 2), and (10, 3); thus, the output is 3. Any other nodes in Treeland have fewer supports to be the incident node.
Input begins with two integers, N M (1 ≤ N ≤ 10,000; 1 ≤ M ≤ 100) denoting the number of nodes in Treeland and the number of reports, respectively. The next N-1 lines, each contains two integers, ai bi (1 ≤ ai, bi ≤ 10,000) denoting that there is an edge connecting node ai and node bi. It is guaranteed that you can move from one node to any other nodes in Treeland via one or more edges. The next M lines, each contains two integers, xi di (1 ≤ xj ≤ N; 0 ≤ dj < N) representing a report saying that the UFO was spotted at a node which distance from node xj is dj. You may safely assume that there exists at least one node within the distance of dj from node xj.
Output in a line an integer representing the output for the given input.
|This is the example given in the problem statement.|
|The two reports are conflicting to each other, and there can only be at most 1 correct report.|
|There is only one report, (2, 1), and it corresponds to either node 1 or node 3.|
|The most probable incident node is either node 1 or node 4. Support for node 1: (1, 0) and (5, 3). Support for node 4: (4, 0) and (5, 3).|
End of Problem