Minmaxtree

Problem Statement

You are given an unweighted tree with N nodes numbered from \(1\) to \(N\) and N-1 edges. Your task is to assign a weight to each edge so that the resulting weighted tree meets K conditions. The conditions come in two types:

• M x y z: On the unique path (chain) from node x to node y, the maximum edge weight must be \(z\). In other words, every edge on the path must have a weight \(\le z\) and at least one edge must have weight exactly \(z\).
• m x y z: On the unique path from node x to node y, the minimum edge weight must be \(z\). That is, every edge on the path must have a weight \(\ge z\) and at least one edge must have weight exactly \(z\).

It is guaranteed that all z values given in the conditions are distinct. Construct one valid assignment of weights to the tree edges that satisfies all the conditions, and output the weights of the N-1 edges in the same order as the input.

inputFormat

Input

The input consists of the following:

1. The first line contains two integers: N and K (N is the number of nodes, and there are N-1 tree edges and K conditions).
2. The next N-1 lines each contain two integers u and v indicating an edge between nodes u and v.
3. The following K lines each contain a condition in one of the two forms:
   • M x y z
   • m x y z
   where M means that the maximum weight on the path from x to y must be \(z\), and m means that the minimum weight on that path must be \(z\).

outputFormat

Output

Output one line containing N-1 integers separated by spaces, which represent the assigned weight for each edge in the same order as the input.

sample

3 2
1 2
2 3
M 1 3 5
m 1 2 3

3 5