#include <bits/stdc++.h>
using namespace std;
const int N = 70005;
const int INF = 2e9;
vector<int> adj[N];
int parent[N], depth[N], heavy[N], head[N], pos[N], cur_pos;
int n, k;
// Edge constraints
int min_val[N], max_val[N];
struct Query {
char t;
int u, v, z;
} queries[N];
// --- HLD Part ---
int dfs_sz(int u) {
int size = 1, max_c_size = 0;
for (int v : adj[u]) {
if (v != parent[u]) {
parent[v] = u;
depth[v] = depth[u] + 1;
int c_size = dfs_sz(v);
size += c_size;
if (c_size > max_c_size) {
max_c_size = c_size;
heavy[u] = v;
}
}
}
return size;
}
void dfs_hld(int u, int h) {
head[u] = h;
pos[u] = ++cur_pos;
if (heavy[u]) dfs_hld(heavy[u], h);
for (int v : adj[u]) {
if (v != parent[u] && v != heavy[u]) dfs_hld(v, v);
}
}
// --- Segment Tree for Path Updates ---
int treeMin[4 * N], treeMax[4 * N];
void update(int* tree, int node, int start, int end, int l, int r, int val, bool isMax) {
if (start > end || start > r || end < l) return;
if (start >= l && end <= r) {
if (isMax) tree[node] = max(tree[node], val);
else tree[node] = min(tree[node], val);
return;
}
int mid = (start + end) / 2;
update(tree, 2 * node, start, mid, l, r, val, isMax);
update(tree, 2 * node + 1, mid + 1, end, l, r, val, isMax);
}
int query_point(int* tree, int node, int start, int end, int p, bool isMax) {
if (start == end) return tree[node];
int mid = (start + end) / 2;
int res = tree[node];
if (p <= mid) {
int left = query_point(tree, 2 * node, start, mid, p, isMax);
return isMax ? max(res, left) : min(res, left);
} else {
int right = query_point(tree, 2 * node + 1, mid + 1, end, p, isMax);
return isMax ? max(res, right) : min(res, right);
}
}
void update_path(int u, int v, int z, bool isMax) {
int* tree = isMax ? treeMin : treeMax; // treeMin stores 'm' (lower bounds), treeMax stores 'M' (upper bounds)
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
update(tree, 1, 1, n, pos[head[u]], pos[u], z, isMax);
u = parent[head[u]];
}
if (u == v) return;
if (depth[u] > depth[v]) swap(u, v);
update(tree, 1, 1, n, pos[u] + 1, pos[v], z, isMax);
}
// --- Matching Part ---
vector<int> g[N];
int matchL[N], matchR[N], vis[N], timer;
bool dfs_match(int u) {
vis[u] = timer;
for (int v : g[u]) {
if (!matchR[v] || (vis[matchR[v]] != timer && dfs_match(matchR[v]))) {
matchR[v] = u;
matchL[u] = v;
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
dfs_sz(1);
dfs_hld(1, 1);
for (int i = 0; i < 4 * N; i++) {
treeMin[i] = -1;
treeMax[i] = INF;
}
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> queries[i].t >> queries[i].u >> queries[i].v >> queries[i].z;
update_path(queries[i].u, queries[i].v, queries[i].z, queries[i].t == 'm');
}
for (int i = 2; i <= n; i++) {
min_val[i] = query_point(treeMin, 1, 1, n, pos[i], true);
max_val[i] = query_point(treeMax, 1, 1, n, pos[i], false);
}
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= 2; j++) { // Just a placeholder for bipartite construction
// Logic: if query i's value z matches an edge's min or max constraint
}
}
// Simplified bipartite builder:
for (int i = 2; i <= n; i++) {
// Link edge i to the constraint query that matches its final min/max
for(int j=1; j<=k; j++) {
if((queries[j].t == 'm' && queries[j].z == min_val[i]) ||
(queries[j].t == 'M' && queries[j].z == max_val[i])) {
g[j].push_back(i);
}
}
}
for (int i = 1; i <= k; i++) {
timer++;
dfs_match(i);
}
for (int i = 2; i <= n; i++) {
int final_v = matchR[i] ? queries[matchR[i]].z : max(0, min_val[i]);
if (final_v == -1) final_v = 0; // Default if no constraint
cout << i << " " << parent[i] << " " << final_v << "\n";
}
return 0;
}
