// https://oj.uz/problem/view/BOI18_minmaxtree
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define el '\n'
#define FNAME "minmaxtree"
#define ll long long
#define int long long
#define ld long double
const int MOD = 1e9 + 7;
const ll INF = 1e18 + 7;
const double EPS = 1e-9;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(FNAME ".in", "r"))
{
freopen(FNAME ".in", "r", stdin);
freopen(FNAME ".out", "w", stdout);
}
return;
}
const int N = 7e4 + 5, K = N;
int n, k, par[N], h[N], heavy[N], head[N], timeDfs = 0, pos[N], ans[N];
vector<int> adj[N];
struct Info
{
char type;
int x, y, z;
};
Info info[K];
struct SegmentTreeMin
{
int n;
vector<int> nodes, lazy;
int merge(int a, int b) { return min(a, b); }
void push(int idx, int l, int r)
{
if (lazy[idx] == INF)
return;
nodes[idx] = min(nodes[idx], lazy[idx]);
if (l != r)
lazy[idx << 1] = min(lazy[idx << 1], lazy[idx]), lazy[(idx << 1) + 1] = min(lazy[(idx << 1) + 1], lazy[idx]);
lazy[idx] = INF;
}
void init(int n) { this->n = n, nodes.assign(4 * n + 5, INF), lazy.assign(4 * n + 5, INF); }
void update(int u, int v, int val) { update(u, v, val, 1, 1, n); }
void update(int u, int v, int val, int idx, int l, int r)
{
push(idx, l, r);
if (r < u || v < l)
return;
if (u <= l && r <= v)
{
lazy[idx] = min(lazy[idx], val);
push(idx, l, r);
return;
}
int mid = (l + r) >> 1;
update(u, v, val, idx << 1, l, mid);
update(u, v, val, (idx << 1) + 1, mid + 1, r);
nodes[idx] = merge(nodes[idx << 1], nodes[(idx << 1) + 1]);
}
int query(int u, int v) { return query(u, v, 1, 1, n); }
int query(int u, int v, int idx, int l, int r)
{
push(idx, l, r);
if (r < u || v < l)
return INF;
if (u <= l && r <= v)
return nodes[idx];
int mid = (l + r) >> 1;
return merge(query(u, v, idx << 1, l, mid),
query(u, v, (idx << 1) + 1, mid + 1, r));
}
};
SegmentTreeMin stMin;
struct SegmentTreeMax
{
int n;
vector<int> nodes, lazy;
int merge(int a, int b) { return max(a, b); }
void push(int idx, int l, int r)
{
if (lazy[idx] == -INF)
return;
nodes[idx] = max(nodes[idx], lazy[idx]);
if (l != r)
lazy[idx << 1] = max(lazy[idx << 1], lazy[idx]), lazy[(idx << 1) + 1] = max(lazy[(idx << 1) + 1], lazy[idx]);
lazy[idx] = -INF;
}
void init(int n) { this->n = n, nodes.assign(4 * n + 5, -INF), lazy.assign(4 * n + 5, -INF); }
void update(int u, int v, int val) { update(u, v, val, 1, 1, n); }
void update(int u, int v, int val, int idx, int l, int r)
{
push(idx, l, r);
if (r < u || v < l)
return;
if (u <= l && r <= v)
{
lazy[idx] = max(lazy[idx], val);
push(idx, l, r);
return;
}
int mid = (l + r) >> 1;
update(u, v, val, idx << 1, l, mid);
update(u, v, val, (idx << 1) + 1, mid + 1, r);
nodes[idx] = merge(nodes[idx << 1], nodes[(idx << 1) + 1]);
}
int query(int u, int v) { return query(u, v, 1, 1, n); }
int query(int u, int v, int idx, int l, int r)
{
push(idx, l, r);
if (r < u || v < l)
return -INF;
if (u <= l && r <= v)
return nodes[idx];
int mid = (l + r) >> 1;
return merge(query(u, v, idx << 1, l, mid),
query(u, v, (idx << 1) + 1, mid + 1, r));
}
};
SegmentTreeMax stMax;
int dfs(int u, int pre)
{
int mxChildSz = 0, sz = 1;
for (int v : adj[u])
{
if (v == pre)
continue;
++sz, par[v] = u, h[v] = h[u] + 1;
int szV = dfs(v, u);
sz += szV;
if (mxChildSz < szV)
mxChildSz = szV, heavy[u] = v;
}
return sz;
}
void hld(int u, int pre, int curHead)
{
head[u] = curHead, ++timeDfs, pos[u] = timeDfs;
if (heavy[u])
hld(heavy[u], u, curHead);
for (int v : adj[u])
{
if (v == pre)
continue;
if (v != heavy[u])
{
hld(v, u, v);
break;
}
}
}
void updateMin(int x, int y, int z)
{
for (; head[x] != head[y]; y = par[head[y]])
{
if (h[head[x]] > h[head[y]])
swap(x, y);
stMax.update(pos[head[y]], pos[y], z);
}
if (h[x] > h[y])
swap(x, y);
stMax.update(x, y, z);
}
void updateMax(int x, int y, int z)
{
for (; head[x] != head[y]; y = par[head[y]])
{
if (h[head[x]] > h[head[y]])
swap(x, y);
stMin.update(pos[head[y]], pos[y], z);
}
if (h[x] > h[y])
swap(x, y);
stMin.update(x, y, z);
}
void solve()
{
cin >> n;
stMin.init(n), stMax.init(n);
// cerr << stMin.query(1, n) << el;
// stMin.update(1, n, 1);
// cerr << stMin.query(1, n) << el;
// cerr << stMin.query(1, 1) << el;
for (int u, v, i = 1; i <= n - 1; ++i)
cin >> u >> v, adj[u].push_back(v), adj[v].push_back(u);
dfs(1, 1), hld(1, 1, 1);
// for (int i = 1; i <= n; ++i)
// cerr << i << ": " << head[i] << " " << heavy[i] << " " << pos[i] << el;
cin >> k;
for (int x, y, z, i = 1; i <= k; ++i)
{
char type;
cin >> type >> x >> y >> z;
// cerr << i << el;
if (type == 'M')
updateMax(x, y, z);
else
updateMin(x, y, z);
// cerr << i << el;
}
// for (int i = 1; i <= n; ++i)
// cerr << i << ": " << stMax.query(pos[i], pos[i]) << " " << stMin.query(pos[i], pos[i]) << el;
set<pair<int, int>> szNode;
vector<int> choices(n + 5);
map<int, set<int>> mnHave, mxHave;
for (int i = 2; i <= n; ++i)
{
int mn = stMax.query(pos[i], pos[i]), mx = stMin.query(pos[i], pos[i]);
mnHave[mn].insert(i), mxHave[mx].insert(i);
// cerr << i << " " << mn << " " << mx << el;
if (mn == -INF && mx == INF)
choices[i] = 0, ans[i] = 0;
else
{
// cerr << i << "!" << (mn == INF) << " " << (mx == -INF) << el;
ans[i] = mn;
if (mn == -INF || mx == INF)
choices[i] = 1, szNode.insert({1, i});
else
choices[i] = 2, szNode.insert({2, i});
}
}
while (!szNode.empty())
{
int u = (*szNode.begin()).second;
szNode.erase(szNode.begin());
// cerr << u << " " << choices[u] << el;
if (choices[u] == 0)
{
}
else if (choices[u] == 1)
{
int mn = stMax.query(pos[u], pos[u]), mx = stMin.query(pos[u], pos[u]);
// cerr << u << " " << choices[u] << " " << mn << " " << mx << el;
if (mn == INF)
{
ans[u] = mx;
for (int v : mxHave[mx])
{
if (v == u)
continue;
stMin.update(pos[v], pos[v], -INF);
szNode.erase({choices[v], v});
choices[v] = max(0ll, choices[v] - 1);
if (!choices[v])
mxHave[v].erase(v);
else
szNode.insert({choices[v], v});
}
}
else
{
ans[u] = mn;
for (int v : mnHave[mn])
{
if (v == u)
continue;
stMax.update(pos[v], pos[v], INF);
szNode.erase({choices[v], v});
choices[v] = max(0ll, choices[v] - 1);
if (!choices[v])
mnHave[v].erase(v);
else
szNode.insert({choices[v], v});
}
}
}
else
{
int mn = stMax.query(pos[u], pos[u]), mx = stMin.query(pos[u], pos[u]);
ans[u] = mx;
for (int v : mxHave[mx])
{
if (v == u)
continue;
stMin.update(pos[v], pos[v], -INF);
szNode.erase({choices[v], v});
choices[v] = max(0ll, choices[v] - 1);
if (!choices[v])
mxHave[v].erase(v);
else
szNode.insert({choices[v], v});
}
}
choices[u] = 0;
}
for (int i = 2; i <= n; ++i)
cout << i << " " << par[i] << " " << ans[i] << el;
return;
}
signed main()
{
setup();
int t = 1;
bool multiTest = false;
if (multiTest)
cin >> t;
while (t--)
solve();
return 0;
}
