#include <bits/stdc++.h>
class IO {
  static const int bufSize = 1 << 18;
  char inBuf[bufSize], outBuf[bufSize];
  char *ip1 = inBuf, *ip2 = inBuf;
  int goodReadBit = 0, op1 = -1, op2 = bufSize - 1;
  __inline__ __attribute__((always_inline)) int gc() {
    return ip1 == ip2 && (ip2 = (ip1 = inBuf) + fread(inBuf, 1, bufSize, stdin),
                          ip1 == ip2)
               ? EOF
               : *ip1++;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void __RI(T &x) {
    int ch = gc(), neg = 1;
    x = 0;
    for (; !(isdigit(ch) || ch == '-' || ch == EOF); ch = gc())
      ;
    if (ch == EOF) {
      goodReadBit = 0;
      return;
    }
    if (ch == '-') neg = -1, ch = gc();
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - 48) * neg;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void __RC(T &x) {
    unsigned char ch;
    while (isspace(ch = gc()))
      ;
    x = ch;
  }
  __inline__ __attribute__((always_inline)) void __RS(std::string &x) {
    char ch;
    x.clear();
    for (ch = gc(); isspace(ch); ch = gc())
      ;
    if (ch == EOF) {
      goodReadBit = 0;
      return;
    }
    for (; !isspace(ch); ch = gc()) x.push_back(ch);
  }

 public:
  __inline__ __attribute__((always_inline)) void R(char &x) { __RC(x); }
  __inline__ __attribute__((always_inline)) void R(unsigned char &x) {
    __RC(x);
  }
  __inline__ __attribute__((always_inline)) void R(std::string &x) { __RS(x); }
  template <typename T1, typename T2>
  __inline__ __attribute__((always_inline)) void R(std::pair<T1, T2> &x) {
    R(x.first), R(x.second);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void R(std::vector<T> &x) {
    for (auto it = x.begin(); it != x.end(); ++it) R(*it);
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void RA(T *a, int n) {
    for (int i = 0; i < n; ++i) R(a[i]);
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void R(T &x, Args &...args) {
    R(x), R(args...);
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void RA(T *a, int n, Args... args) {
    for (int i = 0; i < n; ++i) RA(a[i], args...);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void R(T &x) {
    static_assert(std::is_integral<T>::value, "Unsupported types");
    if (std::is_integral<T>::value) __RI(x);
  }

 private:
  char space;
  __inline__ __attribute__((always_inline)) void pc(const char &x) {
    if (op1 == op2) flush();
    outBuf[++op1] = x;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void __WI(T x) {
    static char buf[64];
    static int len = -1;
    if (x >= 0) {
      do {
        buf[++len] = x % 10 + 48, x /= 10;
      } while (x);
    } else {
      pc('-');
      do {
        buf[++len] = -(x % 10) + 48, x /= 10;
      } while (x);
    }
    while (len >= 0) {
      pc(buf[len]), --len;
    }
  }

 public:
  __inline__ __attribute__((always_inline)) void flush() {
    fwrite(outBuf, 1, op1 + 1, stdout), op1 = -1;
  }
  __inline__ __attribute__((always_inline)) void W(const char &x) { pc(x); }
  __inline__ __attribute__((always_inline)) void W(const char *x) {
    while (*x != '\0') pc(*(x++));
  }
  __inline__ __attribute__((always_inline)) void W(const std::string &x) {
    W(x.c_str());
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void W(const std::vector<T> &x) {
    for (auto it = x.begin(); it != x.end(); it++) WS(*it);
    WL();
  }
  __inline__ __attribute__((always_inline)) void WL() { W('\n'); }
  template <typename T>
  __inline__ __attribute__((always_inline)) void WL(const T &x) {
    W(x), W('\n');
  }
  __inline__ __attribute__((always_inline)) void WS() { W(' '); }
  template <typename T>
  __inline__ __attribute__((always_inline)) void WS(const T &x) {
    W(x), W(space);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void WA(T *a, int n) {
    for (int i = 0; i < n; i++) WS(a[i]);
    WL();
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void W(const T &x,
                                                   const Args &...args) {
    W(x), W(space), W(args...);
  }
  template <typename... Args>
  __inline__ __attribute__((always_inline)) void WL(const Args &...args) {
    W(args...), W('\n');
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void WA(T *a, int n, Args... args) {
    for (int i = 0; i < n; i++) WA(a[i], args...);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void W(const T &x) {
    static_assert(std::is_integral<T>::value, "Unsupported types");
    if (std::is_integral<T>::value) __WI(x);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &operator>>(T &x) {
    R(x);
    return (*this);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &operator<<(const T &x) {
    W(x);
    return (*this);
  }
  IO() { space = ' '; }
} io;
namespace Alphagocc {
decltype(std::chrono::high_resolution_clock::now()) tStart;
};
void TimeBegin() {
  Alphagocc::tStart = std::chrono::high_resolution_clock::now();
}
long long TimeEnd() {
  return (std::chrono::high_resolution_clock::now() - Alphagocc::tStart)
      .count();
}
using namespace std;
const int8_t INFC = 0x3f;
const int16_t INFS = 0x3f3f;
const int32_t INF = 0x3f3f3f3f;
const int64_t INFL = 0x3f3f3f3f3f3f3f3fLL;
namespace std {
template <>
struct hash<pair<int, int>> {
  size_t operator()(pair<int, int> const &p) const {
    size_t const h1(hash<int>{}(p.first));
    size_t const h2(hash<int>{}(p.second));
    return h1 ^ (h2 << 1);
  }
};
}  // namespace std
const int MAXN = 1e4;
vector<int> G[MAXN], road[MAXN];
unordered_map<pair<int, int>, int> edge;
int f[MAXN], endPoint, found;
void dfs(int u, int p, int x) {
  if (found) return;
  road[x].push_back(u);
  if (u == endPoint) {
    found = 1;
    return;
  }
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs(v, u, x);
  }
  if (found) return;
  road[x].pop_back();
}
int main() {
  int n;
  io >> n;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    io >> x >> y;
    --x, --y;
    G[x].push_back(y);
    G[y].push_back(x);
    edge[{x, y}] = edge[{y, x}] = i;
  }
  memset(f, -1, sizeof(f));
  int m;
  io >> m;
  vector<tuple<int, int, int>> v(m);
  for_each(v.begin(), v.end(), [](tuple<int, int, int> &a) {
    io.R(get<0>(a), get<1>(a), get<2>(a));
  });
  sort(v.begin(), v.end(),
       [](const tuple<int, int, int> &a, const tuple<int, int, int> &b) {
         return get<2>(a) > get<2>(b);
       });
  for (int i = 0; i < m; i++)
    endPoint = get<1>(v[i]) - 1, found = 0, dfs(get<0>(v[i]) - 1, -1, i);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < int(road[i].size()) - 1; j++)
      f[edge[{road[i][j], road[i][j + 1]}]] =
          max(f[edge[{road[i][j], road[i][j + 1]}]], get<2>(v[i]));
  }
  bool flg = 1;
  for (int i = 0; i < m && flg; i++) {
    int temp = INF;
    for (int j = 0; j < int(road[i].size()) - 1; j++)
      temp = min(f[edge[{road[i][j], road[i][j + 1]}]], temp);
    if (temp != get<2>(v[i])) flg = 0;
  }
  if (flg) {
    for (int i = 0; i < n; i++)
      if (f[i] == -1) f[i] = 1;
    io.WA(f, n - 1);
  } else
    io.WL(-1);
  io.flush();
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
class IO {
  static const int bufSize = 1 << 18;
  char inBuf[bufSize], outBuf[bufSize];
  char *ip1 = inBuf, *ip2 = inBuf;
  int goodReadBit = 0, op1 = -1, op2 = bufSize - 1;
  __inline__ __attribute__((always_inline)) int gc() {
    return ip1 == ip2 && (ip2 = (ip1 = inBuf) + fread(inBuf, 1, bufSize, stdin),
                          ip1 == ip2)
               ? EOF
               : *ip1++;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void __RI(T &x) {
    int ch = gc(), neg = 1;
    x = 0;
    for (; !(isdigit(ch) || ch == '-' || ch == EOF); ch = gc())
      ;
    if (ch == EOF) {
      goodReadBit = 0;
      return;
    }
    if (ch == '-') neg = -1, ch = gc();
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - 48) * neg;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void __RC(T &x) {
    unsigned char ch;
    while (isspace(ch = gc()))
      ;
    x = ch;
  }
  __inline__ __attribute__((always_inline)) void __RS(std::string &x) {
    char ch;
    x.clear();
    for (ch = gc(); isspace(ch); ch = gc())
      ;
    if (ch == EOF) {
      goodReadBit = 0;
      return;
    }
    for (; !isspace(ch); ch = gc()) x.push_back(ch);
  }

 public:
  __inline__ __attribute__((always_inline)) void R(char &x) { __RC(x); }
  __inline__ __attribute__((always_inline)) void R(unsigned char &x) {
    __RC(x);
  }
  __inline__ __attribute__((always_inline)) void R(std::string &x) { __RS(x); }
  template <typename T1, typename T2>
  __inline__ __attribute__((always_inline)) void R(std::pair<T1, T2> &x) {
    R(x.first), R(x.second);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void R(std::vector<T> &x) {
    for (auto it = x.begin(); it != x.end(); ++it) R(*it);
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void RA(T *a, int n) {
    for (int i = 0; i < n; ++i) R(a[i]);
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void R(T &x, Args &...args) {
    R(x), R(args...);
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void RA(T *a, int n, Args... args) {
    for (int i = 0; i < n; ++i) RA(a[i], args...);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void R(T &x) {
    static_assert(std::is_integral<T>::value, "Unsupported types");
    if (std::is_integral<T>::value) __RI(x);
  }

 private:
  char space;
  __inline__ __attribute__((always_inline)) void pc(const char &x) {
    if (op1 == op2) flush();
    outBuf[++op1] = x;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void __WI(T x) {
    static char buf[64];
    static int len = -1;
    if (x >= 0) {
      do {
        buf[++len] = x % 10 + 48, x /= 10;
      } while (x);
    } else {
      pc('-');
      do {
        buf[++len] = -(x % 10) + 48, x /= 10;
      } while (x);
    }
    while (len >= 0) {
      pc(buf[len]), --len;
    }
  }

 public:
  __inline__ __attribute__((always_inline)) void flush() {
    fwrite(outBuf, 1, op1 + 1, stdout), op1 = -1;
  }
  __inline__ __attribute__((always_inline)) void W(const char &x) { pc(x); }
  __inline__ __attribute__((always_inline)) void W(const char *x) {
    while (*x != '\0') pc(*(x++));
  }
  __inline__ __attribute__((always_inline)) void W(const std::string &x) {
    W(x.c_str());
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void W(const std::vector<T> &x) {
    for (auto it = x.begin(); it != x.end(); it++) WS(*it);
    WL();
  }
  __inline__ __attribute__((always_inline)) void WL() { W('\n'); }
  template <typename T>
  __inline__ __attribute__((always_inline)) void WL(const T &x) {
    W(x), W('\n');
  }
  __inline__ __attribute__((always_inline)) void WS() { W(' '); }
  template <typename T>
  __inline__ __attribute__((always_inline)) void WS(const T &x) {
    W(x), W(space);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void WA(T *a, int n) {
    for (int i = 0; i < n; i++) WS(a[i]);
    WL();
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void W(const T &x,
                                                   const Args &...args) {
    W(x), W(space), W(args...);
  }
  template <typename... Args>
  __inline__ __attribute__((always_inline)) void WL(const Args &...args) {
    W(args...), W('\n');
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) void WA(T *a, int n, Args... args) {
    for (int i = 0; i < n; i++) WA(a[i], args...);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void W(const T &x) {
    static_assert(std::is_integral<T>::value, "Unsupported types");
    if (std::is_integral<T>::value) __WI(x);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &operator>>(T &x) {
    R(x);
    return (*this);
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &operator<<(const T &x) {
    W(x);
    return (*this);
  }
  IO() { space = ' '; }
} io;
namespace Alphagocc {
decltype(std::chrono::high_resolution_clock::now()) tStart;
};
void TimeBegin() {
  Alphagocc::tStart = std::chrono::high_resolution_clock::now();
}
long long TimeEnd() {
  return (std::chrono::high_resolution_clock::now() - Alphagocc::tStart)
      .count();
}
using namespace std;
const int8_t INFC = 0x3f;
const int16_t INFS = 0x3f3f;
const int32_t INF = 0x3f3f3f3f;
const int64_t INFL = 0x3f3f3f3f3f3f3f3fLL;
namespace std {
template <>
struct hash<pair<int, int>> {
  size_t operator()(pair<int, int> const &p) const {
    size_t const h1(hash<int>{}(p.first));
    size_t const h2(hash<int>{}(p.second));
    return h1 ^ (h2 << 1);
  }
};
}  // namespace std
const int MAXN = 1e4;
vector<int> G[MAXN], road[MAXN];
unordered_map<pair<int, int>, int> edge;
int f[MAXN], endPoint, found;
void dfs(int u, int p, int x) {
  if (found) return;
  road[x].push_back(u);
  if (u == endPoint) {
    found = 1;
    return;
  }
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs(v, u, x);
  }
  if (found) return;
  road[x].pop_back();
}
int main() {
  int n;
  io >> n;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    io >> x >> y;
    --x, --y;
    G[x].push_back(y);
    G[y].push_back(x);
    edge[{x, y}] = edge[{y, x}] = i;
  }
  memset(f, -1, sizeof(f));
  int m;
  io >> m;
  vector<tuple<int, int, int>> v(m);
  for_each(v.begin(), v.end(), [](tuple<int, int, int> &a) {
    io.R(get<0>(a), get<1>(a), get<2>(a));
  });
  sort(v.begin(), v.end(),
       [](const tuple<int, int, int> &a, const tuple<int, int, int> &b) {
         return get<2>(a) > get<2>(b);
       });
  for (int i = 0; i < m; i++)
    endPoint = get<1>(v[i]) - 1, found = 0, dfs(get<0>(v[i]) - 1, -1, i);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < int(road[i].size()) - 1; j++)
      f[edge[{road[i][j], road[i][j + 1]}]] =
          max(f[edge[{road[i][j], road[i][j + 1]}]], get<2>(v[i]));
  }
  bool flg = 1;
  for (int i = 0; i < m && flg; i++) {
    int temp = INF;
    for (int j = 0; j < int(road[i].size()) - 1; j++)
      temp = min(f[edge[{road[i][j], road[i][j + 1]}]], temp);
    if (temp != get<2>(v[i])) flg = 0;
  }
  if (flg) {
    for (int i = 0; i < n; i++)
      if (f[i] == -1) f[i] = 1;
    io.WA(f, n - 1);
  } else
    io.WL(-1);
  io.flush();
  return 0;
}

```