#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
struct Edge {
int to, id;
};
int n;
// ---------- HLD ----------
vector<vector<Edge>> g;
vector<int> parent, depth, heavy, sz, head, pos;
vector<int> edgeIdAtPos; // maps position -> original edge id (for edge mapped to child node)
int curPos;
int dfs_sz(int v, int p) {
parent[v] = p;
sz[v] = 1;
heavy[v] = -1;
int maxsz = 0;
for (auto& e : g[v]) {
int to = e.to;
if (to == p) continue;
depth[to] = depth[v] + 1;
int s = dfs_sz(to, v);
if (s > maxsz) {
maxsz = s;
heavy[v] = to;
}
sz[v] += s;
}
return sz[v];
}
void dfs_hld(int v, int h, int pedge_id = -1) {
head[v] = h;
pos[v] = ++curPos;
// map the edge that connects v to parent (if exists) to position pos[v]
if (pedge_id != -1) edgeIdAtPos[pos[v]] = pedge_id;
if (heavy[v] != -1) {
// heavy edge uses same head
int hid = -1;
// find edge id of heavy edge
for (auto& e : g[v])
if (e.to == heavy[v]) {
hid = e.id;
break;
}
dfs_hld(heavy[v], h, hid);
}
for (auto& e : g[v]) {
int to = e.to;
if (to == parent[v] || to == heavy[v]) continue;
dfs_hld(to, to, e.id);
}
}
// ---------- Segment tree supporting range chmax ----------
struct SegChMax {
int n;
vector<int> st, lazy;
SegChMax(int _n = 0) { init(_n); }
void init(int _n) {
n = 1;
while (n < _n)
n <<= 1;
st.assign(2 * n, -INF);
lazy.assign(2 * n, -INF);
}
void apply(int v, int x) {
st[v] = max(st[v], x);
lazy[v] = max(lazy[v], x);
}
void push(int v) {
if (lazy[v] != -INF) {
apply(v << 1, lazy[v]);
apply(v << 1 | 1, lazy[v]);
lazy[v] = -INF;
}
}
void update(int v, int l, int r, int ql, int qr, int x) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
apply(v, x);
return;
}
push(v);
int m = (l + r) >> 1;
update(v << 1, l, m, ql, qr, x);
update(v << 1 | 1, m + 1, r, ql, qr, x);
st[v] = min(st[v << 1], st[v << 1 | 1]); // value not really used except propagation: keep something
}
void update_range(int l, int r, int x) {
if (l > r) return;
update(1, 1, n, l, r, x);
}
int query_point(int v, int l, int r, int posq) {
if (l == r) return st[v];
push(v);
int m = (l + r) >> 1;
if (posq <= m)
return query_point(v << 1, l, m, posq);
else
return query_point(v << 1 | 1, m + 1, r, posq);
}
int query_point(int p) { return query_point(1, 1, n, p); }
};
// ---------- Segment tree supporting range chmin ----------
struct SegChMin {
int n;
vector<int> st, lazy;
SegChMin(int _n = 0) { init(_n); }
void init(int _n) {
n = 1;
while (n < _n)
n <<= 1;
st.assign(2 * n, INF);
lazy.assign(2 * n, INF);
}
void apply(int v, int x) {
st[v] = min(st[v], x);
lazy[v] = min(lazy[v], x);
}
void push(int v) {
if (lazy[v] != INF) {
apply(v << 1, lazy[v]);
apply(v << 1 | 1, lazy[v]);
lazy[v] = INF;
}
}
void update(int v, int l, int r, int ql, int qr, int x) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
apply(v, x);
return;
}
push(v);
int m = (l + r) >> 1;
update(v << 1, l, m, ql, qr, x);
update(v << 1 | 1, m + 1, r, ql, qr, x);
st[v] = max(st[v << 1], st[v << 1 | 1]); // not important, kept for structure
}
void update_range(int l, int r, int x) {
if (l > r) return;
update(1, 1, n, l, r, x);
}
int query_point(int v, int l, int r, int posq) {
if (l == r) return st[v];
push(v);
int m = (l + r) >> 1;
if (posq <= m)
return query_point(v << 1, l, m, posq);
else
return query_point(v << 1 | 1, m + 1, r, posq);
}
int query_point(int p) { return query_point(1, 1, n, p); }
};
// HLD wrapper to update edges on path u-v (edges are mapped to nodes except LCA)
void update_path_edges(int u, int v, int x, bool isLowerUpdate, SegChMax& segL, SegChMin& segU) {
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
int h = head[u];
// update positions pos[h] .. pos[u] (these are nodes) BUT edges correspond to pos[child], so we update whole segment
if (isLowerUpdate)
segL.update_range(pos[h], pos[u], x);
else
segU.update_range(pos[h], pos[u], x);
u = parent[h];
}
// now same head
if (depth[u] < depth[v]) swap(u, v);
// nodes from v..u, but edges exclude v (the LCA), so update pos[v]+1 .. pos[u]
if (pos[v] + 1 <= pos[u]) {
if (isLowerUpdate)
segL.update_range(pos[v] + 1, pos[u], x);
else
segU.update_range(pos[v] + 1, pos[u], x);
}
}
// collect edge positions on path u-v
void collect_edge_positions_on_path(int u, int v, vector<int>& outPos) {
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
int h = head[u];
for (int p = pos[h]; p <= pos[u]; ++p)
outPos.push_back(p);
u = parent[h];
}
if (depth[u] < depth[v]) swap(u, v);
for (int p = pos[v] + 1; p <= pos[u]; ++p)
outPos.push_back(p);
}
// ---------- Hopcroft-Karp ----------
struct HopcroftKarp {
int nL, nR;
vector<vector<int>> adj;
vector<int> dist, pairU, pairV;
HopcroftKarp(int _nL = 0, int _nR = 0) { init(_nL, _nR); }
void init(int _nL, int _nR) {
nL = _nL;
nR = _nR;
adj.assign(nL, {});
pairU.assign(nL, -1);
pairV.assign(nR, -1);
dist.assign(nL, 0);
}
void addEdge(int u, int v) { adj[u].push_back(v); }
bool bfs() {
queue<int> q;
for (int u = 0; u < nL; u++) {
if (pairU[u] == -1) {
dist[u] = 0;
q.push(u);
} else
dist[u] = -1;
}
bool reachable = false;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
int pu = pairV[v];
if (pu != -1 && dist[pu] == -1) {
dist[pu] = dist[u] + 1;
q.push(pu);
}
if (pu == -1) reachable = true;
}
}
return reachable;
}
bool dfs(int u) {
for (int v : adj[u]) {
int pu = pairV[v];
if (pu == -1 || (dist[pu] == dist[u] + 1 && dfs(pu))) {
pairU[u] = v;
pairV[v] = u;
return true;
}
}
dist[u] = -1;
return false;
}
int maxMatching() {
int matching = 0;
while (bfs()) {
for (int u = 0; u < nL; u++)
if (pairU[u] == -1)
if (dfs(u)) matching++;
}
return matching;
}
};
// ---------- main ----------
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
g.assign(n + 1, {});
vector<pair<int, int>> edges(n); // 1-based, store input edges for output order (edges[1..n-1])
for (int i = 1; i <= n - 1; i++) {
int a, b;
cin >> a >> b;
edges[i] = {a, b};
g[a].push_back({b, i});
g[b].push_back({a, i});
}
parent.assign(n + 1, 0);
depth.assign(n + 1, 0);
heavy.assign(n + 1, -1);
sz.assign(n + 1, 0);
head.assign(n + 1, 0);
pos.assign(n + 1, 0);
edgeIdAtPos.assign(n + 2, -1); // positions 1..n
curPos = 0;
depth[1] = 0;
dfs_sz(1, 0);
dfs_hld(1, 1, -1);
// read queries
int q;
cin >> q;
struct Q {
char type;
int u, v;
int x;
int id;
};
vector<Q> queries;
queries.reserve(q);
for (int i = 0; i < q; i++) {
char t;
int u, v, x;
cin >> t >> u >> v >> x;
queries.push_back({t, u, v, x, i});
}
// Build segtrees (size = n because pos runs 1..n). Edge positions are pos[child] (not for root)
SegChMax segL(n + 5);
SegChMin segU(n + 5);
// process queries: for each 'm' (lower bound) we do chmax on path edges; for each 'M' (upper bound) chmin on path edges
for (auto& qu : queries) {
if (qu.type == 'm') { // min on path = x -> edges must be >= x and one edge == x => chmax lower bounds
update_path_edges(qu.u, qu.v, qu.x, true, segL, segU);
} else { // 'M' max on path = x -> edges must be <= x and one edge == x => chmin upper bounds
update_path_edges(qu.u, qu.v, qu.x, false, segL, segU);
}
}
// collect final L and U for each edge (by its pos)
int mEdges = n - 1;
vector<int> Lpos(n + 2), Upos(n + 2);
for (int p = 2; p <= n; ++p) { // pos[root] may be 1; edges are mapped to nodes except root
Lpos[p] = segL.query_point(p);
Upos[p] = segU.query_point(p);
}
// For safety assign for pos==1 too (unused)
Lpos[1] = segL.query_point(1);
Upos[1] = segU.query_point(1);
// Check consistency: for every edge (pos mapping) L <= U
bool ok = true;
for (int p = 2; p <= n; p++) {
if (Lpos[p] > Upos[p]) {
ok = false;
break;
}
}
if (!ok) {
cout << -1 << '\n';
return 0;
}
// Build adjacency for bipartite matching:
// left = queries (all q), right = edges (indices 1..mEdges -> we'll remap to 0..mEdges-1)
HopcroftKarp hk(q, mEdges);
// For each query, collect positions on path and add an edge to each edge id that can host that query's x
for (int i = 0; i < q; i++) {
auto& qu = queries[i];
vector<int> poslist;
collect_edge_positions_on_path(qu.u, qu.v, poslist);
for (int p : poslist) {
if (p <= 0 || p > n) continue;
int l = Lpos[p], uval = Upos[p];
if (l <= qu.x && qu.x <= uval) {
int eId = edgeIdAtPos[p]; // original edge id (1..n-1)
if (eId == -1) continue;
hk.addEdge(i, eId - 1); // map edge id to 0-based
}
}
}
int matching = hk.maxMatching();
if (matching < q) {
cout << -1 << '\n';
return 0;
}
// construct weights for edges
vector<int> weight(n, 1000000000);
// for each matched right vertex (edge), hk.pairV[edge] gives query id
for (int e = 0; e < mEdges; e++) {
int qid = hk.pairV[e];
int pos_of_edge = -1;
// find pos for this edge id: we have edgeIdAtPos[pos] = e+1
// Instead of searching, build reverse map:
// Let's build reverse map once:
}
// build reverse map pos -> edgeId already edgeIdAtPos; let's build edgeId -> pos
vector<int> edgePos(mEdges + 1, -1); // 1..mEdges
for (int p = 1; p <= n; p++) {
int eid = edgeIdAtPos[p];
if (eid != -1) edgePos[eid] = p;
}
// assign weights for matched edges
for (int e = 1; e <= mEdges; e++) {
int matchedQuery = hk.pairV[e - 1];
int p = edgePos[e];
if (matchedQuery != -1) {
weight[e] = queries[matchedQuery].x;
} else {
// choose a value inside [Lpos[p], Upos[p]]
int chosen;
if (Lpos[p] != -INF)
chosen = Lpos[p];
else if (Upos[p] != INF)
chosen = Upos[p];
else
chosen = 1000000000;
// ensure chosen in interval
if (chosen < Lpos[p]) chosen = Lpos[p];
if (chosen > Upos[p]) chosen = Upos[p];
weight[e] = chosen;
}
}
// print edges in original order: a b weight
for (int i = 1; i <= mEdges; i++) {
cout << edges[i].first << ' ' << edges[i].second << ' ' << weight[i] << '\n';
}
return 0;
}
