#include <bits/stdc++.h>
using namespace std;
#define el '\n'
const int MAXN = 70005;
const int NEG_INF = -1000000000;
const int INF = 1000000000;
struct Query {
bool type; // 1 for 'M' (max), 0 for 'm' (min)
int u, v;
int w;
Query(char x='#', int U=0, int V=0, int W=0) {
type = (x == 'M' ? 1 : 0);
u = U; v = V; w = W;
}
};
int n, q;
vector<int> graph[MAXN];
vector<Query> queryv; // 1..q
int uID[MAXN], vID[MAXN]; // original edges in input order
// ------------ Hopcroft-Karp (kept your structure) --------------
struct Hopcorft {
int nL, nR;
vector<vector<int>> graph; // adjacency left -> list of right indices
vector<int> matchLeft, matchRight;
vector<int> distancia;
Hopcorft(int l = 0, int r = 0) { init(l,r); }
void init(int l, int r) {
nL = l; nR = r;
graph.assign(nL+1, {});
matchLeft.assign(nL+1, 0);
matchRight.assign(nR+1, 0);
distancia.assign(nL+1, 0);
}
void addEdge(int u, int v) { // u in [1..nL], v in [1..nR]
if (u<=0 || v<=0) return;
graph[u].push_back(v);
}
bool bfs() {
queue<int> qu;
for (int u=1; u<=nL; ++u) {
if (!matchLeft[u]) { distancia[u] = 0; qu.push(u); }
else distancia[u] = INF;
}
distancia[0] = INF;
while (!qu.empty()) {
int u = qu.front(); qu.pop();
if (distancia[u] >= distancia[0]) continue;
for (int v : graph[u]) {
int paired = matchRight[v]; // left index matched to v or 0
if (distancia[paired] == INF) {
distancia[paired] = distancia[u] + 1;
qu.push(paired);
}
}
}
return (distancia[0] != INF);
}
bool dfs(int u) {
if (!u) return true;
for (int v : graph[u]) {
if (distancia[ matchRight[v] ] == distancia[u] + 1 && dfs(matchRight[v])) {
matchRight[v] = u;
matchLeft[u] = v;
return true;
}
}
distancia[u] = INF;
return false;
}
int maxMatching() {
int match = 0;
while (bfs()) {
for (int u=1; u<=nL; ++u)
if (!matchLeft[u] && dfs(u)) match++;
}
return match;
}
// write matched query weights into res[edge_id]
void getW(vector<int> &res) {
maxMatching();
for (int u=1; u<=nL; ++u) {
if (matchLeft[u]) {
int e = matchLeft[u]; // matched edge id (right side)
res[e] = queryv[u].w; // query index u matched to edge e
}
}
}
};
// ---------- events for sweepline (store w,type,id) ----------
struct Ev { int w; int type; int id; };
vector<Ev> eventA[MAXN], eventR[MAXN]; // index by HLD position
inline void rangeAddEvent(int l, int r, int w, int type, int id) {
if (l > r) return;
eventA[l].push_back({w,type,id});
eventR[r].push_back({w,type,id});
}
// ----------------- HLD -----------------
int timedfs = 1, curChain = 1, edgecnt = 0;
int eID[MAXN]; // eID[u] = edge id for parent[u]-u (0 for root)
int parentArr[MAXN];
int pos[MAXN], arrPos[MAXN];
namespace HeavyLight {
vector<int> chainHead, chainID;
vector<int> depth, sz;
void dfs(int u, int pre) {
parentArr[u] = pre;
for (int v : graph[u]) if (v != pre) {
depth[v] = depth[u] + 1;
dfs(v,u);
sz[u] += sz[v];
}
}
void HLD(int u, int pre) {
if (!chainHead[curChain]) chainHead[curChain] = u;
chainID[u] = curChain;
pos[u] = timedfs;
arrPos[timedfs] = u;
timedfs++;
if (u == pre) eID[u] = 0; // root sentinel (we keep parent[root]=root)
else eID[u] = ++edgecnt;
int nxt = -1;
for (int v : graph[u]) if (v != pre) {
if (nxt == -1 || sz[v] > sz[nxt]) nxt = v;
}
if (nxt != -1) HLD(nxt, u);
for (int v : graph[u]) if (v != pre && v != nxt) {
curChain++;
HLD(v, u);
}
}
// add path events using positions
void addEvent(int u, int v, int w, int type, int id) {
while (chainHead[chainID[u]] != chainHead[chainID[v]]) {
if (depth[chainHead[chainID[u]]] < depth[chainHead[chainID[v]]]) swap(u,v);
int L = pos[ chainHead[ chainID[u] ] ];
int R = pos[u];
rangeAddEvent(L, R, w, type, id);
u = parentArr[ chainHead[ chainID[u] ] ];
}
if (depth[u] < depth[v]) swap(u,v);
if (u != v) {
// we need edges under v..u, which map to positions pos[v]+1 .. pos[u]
rangeAddEvent(pos[v] + 1, pos[u], w, type, id);
}
}
void initHLD() {
chainHead.assign(n+2, 0);
chainID.assign(n+2, 0);
depth.assign(n+2, 0);
sz.assign(n+2, 1);
// keep parent[root]=root sentinel
dfs(1, 1);
HLD(1, 1);
}
}
using namespace HeavyLight;
// ---------------- input ----------------
void readInput() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i=1;i<n;i++){
int u,v; cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
uID[i] = u; vID[i] = v;
}
cin >> q;
queryv.resize(q+1);
for (int i=1;i<=q;i++){
char c; int u,v,w; cin >> c >> u >> v >> w;
queryv[i] = Query(c,u,v,w);
}
}
// ---------------- solve ----------------
int main(){
readInput();
initHLD();
// build events (use query index as id)
for (int i=1;i<=q;i++){
addEvent(queryv[i].u, queryv[i].v, queryv[i].w, queryv[i].type, i);
}
// per-edge info
vector<int> loVal(edgecnt+1, NEG_INF), hiVal(edgecnt+1, INF);
vector<int> loId(edgecnt+1, 0), hiId(edgecnt+1, 0);
// active sets store (w,id)
multiset<pair<int,int>> activeMin, activeMax;
// sweep positions 1..n
for (int cur = 1; cur <= n; ++cur) {
// add events starting here
for (auto &ev : eventA[cur]) {
if (ev.type) activeMax.insert({ev.w, ev.id}); // M queries -> activeMax
else activeMin.insert({ev.w, ev.id}); // m queries -> activeMin
}
int u = arrPos[cur];
int e = eID[u]; // if 0 skip (root)
if (e) {
if (!activeMax.empty()) {
auto it = activeMax.begin(); // smallest max constraint
if (it->first < hiVal[e]) { hiVal[e] = it->first; hiId[e] = it->second; }
}
if (!activeMin.empty()) {
auto it = prev(activeMin.end()); // largest min constraint
if (it->first > loVal[e]) { loVal[e] = it->first; loId[e] = it->second; }
}
}
// remove events ending here
for (auto &ev : eventR[cur]) {
if (ev.type) {
auto it = activeMax.find({ev.w, ev.id});
if (it != activeMax.end()) activeMax.erase(it);
} else {
auto it = activeMin.find({ev.w, ev.id});
if (it != activeMin.end()) activeMin.erase(it);
}
}
}
// Build matching graph: Left = queries 1..q, Right = edges 1..edgecnt
Hopcorft karp(q, edgecnt);
for (int e=1; e<=edgecnt; ++e) {
if (loId[e]) karp.addEdge(loId[e], e);
if (hiId[e] && hiId[e] != loId[e]) karp.addEdge(hiId[e], e);
}
// default assign per-edge value within [loVal, hiVal]
vector<int> res(edgecnt+1, 0);
for (int e=1;e<=edgecnt;++e) {
int val = 0;
if (loVal[e] != NEG_INF) val = max(val, loVal[e]);
if (hiVal[e] != INF) val = min(val, hiVal[e]);
// if inconsistent (lo > hi), we still put something; judge problem usually guarantees feasibility
res[e] = val;
}
// run matching and overwrite matched edges with exact query w
karp.getW(res);
// map edges to input order: normalize endpoints
auto norm = [](int a,int b)->pair<int,int>{ if (a>b) swap(a,b); return {a,b}; };
unordered_map<long long,int> toEID;
toEID.reserve(edgecnt*2);
auto key = [](int a,int b)->long long { if (a>b) swap(a,b); return ( (long long)a<<32 ) ^ (long long)b; };
for (int v=2; v<=n; ++v) {
int u = parentArr[v];
toEID[key(u,v)] = eID[v];
}
// print in the original input order
for (int i=1;i<n;i++){
int a = uID[i], b = vID[i];
int e = toEID[key(a,b)];
cout << a << ' ' << b << ' ' << res[e] << el;
}
return 0;
}
