#include <bits/stdc++.h>
/*
*/
constexpr int INF = 1000000000;
struct Edge {
int to, id;
};
int n;
std::vector<std::vector<Edge>> g;
std::vector<int> parent_, depth_, heavy, sz, head, pos;
std::vector<int> invPos;
std::vector<int> edgeIdAtPos;
int curPos;
int dfs_sz(int v, int p) {
parent_[v] = p;
sz[v] = 1;
heavy[v] = -1;
int best = 0;
for (auto& e : g[v]) {
if (e.to == p) continue;
depth_[e.to] = depth_[v] + 1;
int s = dfs_sz(e.to, v);
if (s > best) {
best = s;
heavy[v] = e.to;
}
sz[v] += s;
}
return sz[v];
}
void dfs_hld(int v, int h, int pedge_id = -1) {
head[v] = h;
pos[v] = ++curPos;
invPos[pos[v]] = v;
if (pedge_id != -1) edgeIdAtPos[pos[v]] = pedge_id; // map edge (v-parent[v]) to pos[v]
if (heavy[v] != -1) {
int hid = -1;
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]) {
if (e.to == parent_[v] || e.to == heavy[v]) continue;
dfs_hld(e.to, e.to, e.id);
}
}
struct SegChMax {
int n;
std::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] = std::max(st[v], x);
lazy[v] = std::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);
}
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 p) {
if (l == r) return st[v];
push(v);
int m = (l + r) >> 1;
if (p <= m)
return query_point(v << 1, l, m, p);
else
return query_point(v << 1 | 1, m + 1, r, p);
}
int query_point(int p) { return query_point(1, 1, n, p); }
};
struct SegChMin {
int n;
std::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] = std::min(st[v], x);
lazy[v] = std::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);
}
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 p) {
if (l == r) return st[v];
push(v);
int m = (l + r) >> 1;
if (p <= m)
return query_point(v << 1, l, m, p);
else
return query_point(v << 1 | 1, m + 1, r, p);
}
int query_point(int p) { return query_point(1, 1, n, p); }
};
inline void update_path_edges(int u, int v, int x, bool isLower, SegChMax& segL, SegChMin& segU) {
while (head[u] != head[v]) {
if (depth_[head[u]] < depth_[head[v]]) std::swap(u, v);
int h = head[u];
if (isLower)
segL.update_range(pos[h], pos[u], x);
else
segU.update_range(pos[h], pos[u], x);
u = parent_[h];
}
if (depth_[u] < depth_[v]) std::swap(u, v);
if (pos[v] + 1 <= pos[u]) {
if (isLower)
segL.update_range(pos[v] + 1, pos[u], x);
else
segU.update_range(pos[v] + 1, pos[u], x);
}
}
template<class F>
inline void for_each_path_segment(int u, int v, const F& op) {
while (head[u] != head[v]) {
if (depth_[head[u]] < depth_[head[v]]) std::swap(u, v);
int h = head[u];
op(pos[h], pos[u], h);
u = parent_[h];
}
if (depth_[u] < depth_[v]) std::swap(u, v);
if (pos[v] + 1 <= pos[u]) {
int h = head[u];
op(pos[v] + 1, pos[u], h);
}
}
struct HopcroftKarp {
int nL, nR;
std::vector<std::vector<int>> adj;
std::vector<int> dist, pairU, pairV, it;
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.resize(nL);
it.resize(nL);
}
inline void addEdge(int u, int v) { adj[u].push_back(v); }
bool bfs() {
std::queue<int> q;
bool reachable = false;
for (int u = 0; u < nL; u++) {
if (pairU[u] == -1) {
dist[u] = 0;
q.push(u);
} else
dist[u] = -1;
}
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& k = it[u]; k < (int)adj[u].size(); ++k) {
int v = adj[u][k];
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()) {
fill(it.begin(), it.end(), 0);
for (int u = 0; u < nL; u++)
if (pairU[u] == -1)
if (dfs(u)) matching++;
}
return matching;
}
};
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n;
g.assign(n + 1, {});
std::vector<std::pair<int, int>> kra(n);
for (int i = 1; i <= n - 1; i++) {
int a, b;
std::cin >> a >> b;
kra[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);
invPos.assign(n + 2, 0);
edgeIdAtPos.assign(n + 2, -1);
curPos = 0;
depth_[1] = 0;
dfs_sz(1, 0);
dfs_hld(1, 1, -1);
int q;
std::cin >> q;
struct Q {
char type;
int u, v, x, id;
};
std::vector<Q> queries;
queries.reserve(q);
for (int i = 0; i < q; i++) {
char t;
int u, v, x;
std::cin >> t >> u >> v >> x;
queries.push_back({t, u, v, x, i});
}
SegChMax segL(n + 5);
SegChMin segU(n + 5);
for (auto& qu : queries) {
if (qu.type == 'm') {
update_path_edges(qu.u, qu.v, qu.x, true, segL, segU);
} else {
update_path_edges(qu.u, qu.v, qu.x, false, segL, segU);
}
}
std::vector<int> Lpos(n + 2), Upos(n + 2);
for (int p = 1; p <= n; p++) {
Lpos[p] = segL.query_point(p);
Upos[p] = segU.query_point(p);
}
for (int p = 2; p <= n; p++) {
if (Lpos[p] > Upos[p]) {
std::cout << -1 << "\n";
return 0;
}
}
std::vector<int> chainIndex(n + 1, -1);
int chains = 0;
for (int v = 1; v <= n; v++) {
if (head[v] == v) chainIndex[v] = chains++;
}
std::vector<std::set<int>> active(chains);
struct PInfo {
int p, L, U, cidx;
};
std::vector<PInfo> pinfos;
pinfos.reserve(n - 1);
for (int p = 2; p <= n; p++) {
int node = invPos[p];
int h = head[node];
int cidx = chainIndex[h];
if (edgeIdAtPos[p] != -1) {
pinfos.push_back({p, Lpos[p], Upos[p], cidx});
}
}
std::vector<int> orderByL(pinfos.size()), orderByU(pinfos.size());
std::iota(orderByL.begin(), orderByL.end(), 0);
std::iota(orderByU.begin(), orderByU.end(), 0);
std::sort(orderByL.begin(), orderByL.end(), [&](int a, int b) { return pinfos[a].L < pinfos[b].L; });
std::sort(orderByU.begin(), orderByU.end(), [&](int a, int b) { return pinfos[a].U < pinfos[b].U; });
std::vector<int> qord(q);
std::iota(qord.begin(), qord.end(), 0);
std::sort(qord.begin(), qord.end(), [&](int a, int b) { return queries[a].x < queries[b].x; });
int mEdges = n - 1;
HopcroftKarp hk(q, mEdges);
int aptr = 0, rptr = 0;
for (int idx : qord) {
int x = queries[idx].x;
while (aptr < (int)orderByL.size() && pinfos[orderByL[aptr]].L <= x) {
const auto& pf = pinfos[orderByL[aptr]];
if (pf.L <= pf.U) active[pf.cidx].insert(pf.p);
++aptr;
}
while (rptr < (int)orderByU.size() && pinfos[orderByU[rptr]].U < x) {
const auto& pf = pinfos[orderByU[rptr]];
auto it = active[pf.cidx].find(pf.p);
if (it != active[pf.cidx].end()) active[pf.cidx].erase(it);
++rptr;
}
auto add_in_segment = [&](int l, int r, int chainHead) {
int cidx = chainIndex[chainHead];
auto& S = active[cidx];
auto it = S.lower_bound(l);
while (it != S.end() && *it <= r) {
int p = *it;
int eId = edgeIdAtPos[p];
if (eId != -1) {
hk.addEdge(queries[idx].id, eId - 1);
}
++it;
}
};
for_each_path_segment(queries[idx].u, queries[idx].v, add_in_segment);
}
int matching = hk.maxMatching();
if (matching < q) {
std::cout << -1 << "\n";
return 0;
}
std::vector<int> edgePos(mEdges + 1, -1);
for (int p = 1; p <= n; p++) {
int eid = edgeIdAtPos[p];
if (eid != -1) edgePos[eid] = p;
}
std::vector<int> weight(n, 1000000000);
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 {
int chosen;
if (Lpos[p] != -INF)
chosen = Lpos[p];
else if (Upos[p] != INF)
chosen = Upos[p];
else
chosen = 1000000000;
if (chosen < Lpos[p]) chosen = Lpos[p];
if (chosen > Upos[p]) chosen = Upos[p];
weight[e] = chosen;
}
}
for (int i = 1; i <= mEdges; i++) {
std::cout << kra[i].first << ' ' << kra[i].second << ' ' << weight[i] << '\n';
}
return 0;
}
