Problem: There are n railway stations in Berland. They are connected to each other by n-1 railway sections. The railway network is connected, i.e. can be represented as an undirected tree.

You have a map of that network, so for each railway section you know which stations it connects.

Each of the n-1 sections has some integer value of the scenery beauty. However, these values are not marked on the map and you don't know them. All these values are from 1 to 10^6 inclusive.

You asked m passengers some questions: the j-th one told you three values:

  * his departure station a_j; 
  * his arrival station b_j; 
  * minimum scenery beauty along the path from a_j to b_j (the train is moving along the shortest path from a_j to b_j). 



You are planning to update the map and set some value f_i on each railway section — the scenery beauty. The passengers' answers should be consistent with these values.

Print any valid set of values f_1, f_2, ..., f_{n-1}, which the passengers' answer is consistent with or report that it doesn't exist.

Input

The first line contains a single integer n (2 ≤ n ≤ 5000) — the number of railway stations in Berland.

The next n-1 lines contain descriptions of the railway sections: the i-th section description is two integers x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i), where x_i and y_i are the indices of the stations which are connected by the i-th railway section. All the railway sections are bidirected. Each station can be reached from any other station by the railway.

The next line contains a single integer m (1 ≤ m ≤ 5000) — the number of passengers which were asked questions. Then m lines follow, the j-th line contains three integers a_j, b_j and g_j (1 ≤ a_j, b_j ≤ n; a_j ≠ b_j; 1 ≤ g_j ≤ 10^6) — the departure station, the arrival station and the minimum scenery beauty along his path.

Output

If there is no answer then print a single integer -1.

Otherwise, print n-1 integers f_1, f_2, ..., f_{n-1} (1 ≤ f_i ≤ 10^6), where f_i is some valid scenery beauty along the i-th railway section.

If there are multiple answers, you can print any of them.

Examples

Input


4
1 2
3 2
3 4
2
1 2 5
1 3 3


Output


5 3 5


Input


6
1 2
1 6
3 1
1 5
4 1
4
6 1 3
3 4 1
6 5 2
1 2 5


Output


5 3 1 2 1 


Input


6
1 2
1 6
3 1
1 5
4 1
4
6 1 1
3 4 3
6 5 3
1 2 4


Output


-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int si();
long long sl();
string ss(int);
char sc();
float sf();
double sd();
long double sld();
template <typename T>
void print(T, char = '\n');
template <typename T, typename... Args>
void print(T, Args...);
void pi(const int&, char = '\n');
void pl(const long long&, char = '\n');
void pf(const float&, char = '\n');
void pc(const char&, char = '\n');
void pd(const double&, char = '\n');
void pld(const long double&, char = '\n');
void ps(const string&, char = '\n');
template <typename T>
void pv(const vector<T>& v, char = ' ', char = '\n');
template <typename It>
void out(It begin, It end, char = ' ', char = '\n');
long long russian(long long, long long, long long);
long long fastpow(long long, long long, long long);
long long slowpow(long long, long long, long long);
long long _gcd(long long, long long);
long long _lcm(long long, long long);
long long extgcd(long long, long long, long long&, long long&);
long long _inv(long long, long long);
const int INF = 1e9;
const long long LINF = 1e18;
const int N = 5e3 + 7;
vector<pair<int, int> > G[N];
int vals[N], pre[N];
bool done[N];
pair<int, int> par[N];
pair<int, vector<int> > qu[N];
int TIME;
void dfs(int v, int p, int id) {
  par[v] = {p, id};
  pre[v] = TIME++;
  for (auto&& [s, id] : G[v])
    if (s != p) dfs(s, v, id);
}
int main() {
  int n = si();
  for (int i = 0; i < n - 1; ++i) {
    int u = si(), v = si();
    G[u].push_back({v, i});
    G[v].push_back({u, i});
  }
  dfs(1, 1, -1);
  int q = si();
  for (int i = 0; i < q; ++i) {
    int u = si(), v = si();
    int val = si();
    if (pre[u] > pre[v]) swap(u, v);
    while (pre[v] > pre[u]) {
      if (qu[v].first == val)
        qu[v].second.push_back(i);
      else if (qu[v].first < val)
        qu[v] = {val, {i}};
      v = par[v].first;
    }
    while (u != v) {
      if (qu[u].first == val)
        qu[u].second.push_back(i);
      else if (qu[u].first < val)
        qu[u] = {val, {i}};
      u = par[u].first;
    }
  }
  for (int i = 2; i <= n; ++i) {
    vals[par[i].second] = qu[i].first;
    for (int& v : qu[i].second) done[v] = true;
  }
  bool good = true;
  for (int i = 0; i < q; ++i)
    if (!done[i]) {
      good = false;
      break;
    }
  if (!good) {
    pi(-1);
    return 0;
  }
  for (int i = 0; i < n - 1; ++i) pi(vals[i] ? vals[i] : 1, ' ');
  return 0;
}
template <typename T>
T scanf_t(string&& token) {
  T a;
  scanf(token.c_str(), &a);
  return a;
}
int si() { return scanf_t<int>("%d"); }
long long sl() { return scanf_t<long long>("%lld"); }
string ss(int n) {
  char T[n + 7];
  scanf("%s", T);
  return string(T);
}
char sc() { return scanf_t<char>(" %c"); }
float sf() { return scanf_t<float>("%f"); }
double sd() { return scanf_t<double>("%lf"); }
long double sld() { return scanf_t<long double>("%Lf"); }
template <typename T>
void print(T a, char sep) {
  string token;
  if (is_same<T, int>::value)
    token = "%d";
  else if (is_same<T, long long>::value)
    token = "%lld";
  else if (is_same<T, string>::value)
    token = "%s";
  else if (is_same<T, char>::value)
    token = "%c";
  else if (is_same<T, float>::value)
    token = "%.6f";
  else if (is_same<T, double>::value)
    token = "%.8lf";
  else if (is_same<T, long double>::value)
    token = "%.10Lf";
  token.push_back(sep);
  printf(token.c_str(), a);
}
template <typename T, typename... Args>
void print(T first, Args... rest) {
  print(first, ' ');
  print(rest...);
}
void pi(const int& a, char sep) { printf("%d%c", a, sep); }
void pl(const long long& a, char sep) { printf("%lld%c", a, sep); }
void pf(const float& a, char sep) { printf("%.6f%c", a, sep); }
void pc(const char& a, char sep) { printf("%c%c", a, sep); }
void pd(const double& a, char sep) { printf("%.8lf%c", a, sep); }
void pld(const long double& a, char sep) { printf("%.10Lf%c", a, sep); }
void ps(const string& a, char sep) { printf("%s%c", a.c_str(), sep); }
template <typename It>
void out(It begin, It end, char sep, char endl) {
  while (begin + 1 != end) print(*begin, sep), ++begin;
  if (begin != end) print(*begin, ' '), printf("%c", endl);
}
template <typename T>
void pv(const vector<T>& v, char sep, char endl) {
  out(v.begin(), v.end(), sep, endl);
}
long long russian(long long a, long long k, long long m) {
  long long res = 0;
  while (k) {
    if (k & 1LL) res = (res + a) % m;
    a = (a + a) % m;
    k >>= 1LL;
  }
  return res;
}
long long fastpow(long long a, long long k, long long m) {
  long long res = 1;
  while (k) {
    if (k & 1LL) res = (res * a) % m;
    a = (a * a) % m;
    k >>= 1LL;
  }
  return res;
}
long long slowpow(long long a, long long k, long long m) {
  long long res = 1;
  while (k) {
    if (k & 1LL) res = russian(res, a, m);
    a = russian(a, a, m);
    k >>= 1LL;
  }
  return res;
}
long long _gcd(long long a, long long b) {
  while (b) swap(a %= b, b);
  return a;
}
long long _lcm(long long a, long long b) { return a / _gcd(a, b) * b; }
long long extgcd(long long a, long long b, long long& k, long long& l) {
  if (b == 0) {
    k = 1;
    l = 0;
    return a;
  }
  long long res = extgcd(a, a % b, l, k);
  l -= a / b * k;
  return res;
}
long long _inv(long long a, long long p) { return fastpow(a, p - 2, p); }