시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB60151429.167%

문제

Tanaka has recently solved a classical problem: given some tree with N vertices and weights on the edges, he found the maximum or minimum weight on K chains in the tree. Interestingly, all of these results were distinct! However, unfortunately, the weights from the original tree were lost.

Given Tanaka’s results, as well as the structure of the original tree, can you find some plausible assignment of weights for all edges? If you do, Groot will fall in love with the tree and you will be rewarded 100 points.

입력

The first line of the input will contain the integer N.

The next N − 1 lines of the input will contain a space-separated pair of integers (x, y) , with 1 ≤ x, y ≤ N that signifies that the tree has an edge from node x to node y. The nodes of the tree are indexed from 1 to N.

The next line of the input will contain the integer K.

The next K lines will contain a description of Tanaka’s query results, one result on each line. A result that signifies that the maximum on the path from node x to node y was z will be encoded as ”M x y z”, and one that signifies that the minimum on the path from node x to node y was z will be encoded as ”m x y z”.

It is guaranteed that the given edges form a tree, and that all z values are distinct.

출력

The output file should contain N − 1 lines, each containing three integers x y v that signify that in your assignment of weights to edges there exists an edge between node x and node y having weight v. These edges should be the same as the edges in the input file, ignoring their order. Also, the order of vertices x and y within an edge does not matter. These should lead to the described results. Also, v should be able to fit in a signed 32 bit integer.

It is guaranteed that some assignment of weights leads to the described results.

제한

  • 1 ≤ N ≤ 70,000
  • 1 ≤ K ≤ 70,000
  • 1 ≤ z ≤ 1,000,000,000

예제 입력 1

4
1 2
2 3
3 4
3
M 1 2 1
m 1 4 0
M 2 3 100

예제 출력 1

3 2 100
1 2 1
4 3 0