Problem Description

Translated from BalkanOI 2018 Day 1 T3 “Minmaxtree”.

There is an unweighted tree with $N$ nodes, numbered $1 \dots N$. You need to assign a weight to each edge to make it a weighted tree. The weighted tree must satisfy $K$ conditions. There are two types of conditions:

1. $\ \texttt{M }x\ y\ z\ \$ The maximum edge weight on the path from node $x$ to node $y$ is $z$.
2. $\ \texttt{m }x\ y\ z\ \$ The minimum edge weight on the path from node $x$ to node $y$ is $z$.

It is guaranteed that the $z$ values in these $K$ conditions are all distinct.

Please construct such a tree and output the weight of each edge.

Input Format

The first line contains an integer $N$.
In the next $N - 1$ lines, each line contains two integers, indicating an edge connecting two nodes.
Line $N + 1$ contains an integer $K$.
In the next $K$ lines, each line starts with a letter $\texttt{M}$ or $\texttt{m}$, followed by three integers $x, y, z$.

Output Format

Output $N - 1$ lines. Each line contains three integers $x, y, v$ separated by spaces, meaning an edge $(x, y)$ in the weighted tree has weight $v$.

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

3 2 100
1 2 1
4 3 0

Hint

Subtask #1 (7 points): $1 \le N, z \le 1000$.
Subtask #2 (22 points): Only condition type 1, and no condition type 2.
Subtask #3 (29 points): All paths from $x$ to $y$ given in condition type 1 are pairwise edge-disjoint. All paths from $x$ to $y$ given in condition type 2 are also pairwise edge-disjoint.
Subtask #4 (42 points): No other restrictions.
For all testdata, $1 \le N, K \le 70000$, $0 \le z \le 10^9$.

Thanks to Planet6174 for providing the translation.

Translated by ChatGPT 5