Problem: There is a tree with n vertices. There are also m ants living on it. Each ant has its own color. The i-th ant has two favorite pairs of vertices: (a_i, b_i) and (c_i, d_i). You need to tell if it is possible to paint the edges of the tree in m colors so that every ant will be able to walk between vertices from one of its favorite pairs using only edges of his color; if it is possible, you need to print which pair every ant should use.

Input

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of vertices.

Each of the next n-1 lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n), meaning that there is an edge between vertices u_i and v_i.

The next line contains a single integer m (1 ≤ m ≤ 10^4) — the number of ants.

Each of the next m lines contains four integers a_i, b_i, c_i, and d_i (1 ≤ a_i, b_i, c_i, d_i ≤ n, a_i ≠ b_i, c_i ≠ d_i), meaning that pairs (a_i, b_i) and (c_i, d_i) are favorite for the i-th ant.

Output

Print "NO" (without quotes) if the wanted painting is impossible.

Otherwise, print "YES" (without quotes). Print m lines. On the i-th line, print 1 if the i-th ant will use the first pair and 2 otherwise. If there are multiple answers, print any.

Examples

Input

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


Output

YES
2
1
2


Input

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


Output

NO

Note

In the sample, the second and the third edge should be painted in the first color, the first and the fifth should be painted in the second color, and the fourth should be painted in the third color.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <class T>
struct _iter_wrapper {
  T begin_, end_;
  T begin() { return begin_; }
  T end() { return end_; }
};
template <class T>
_iter_wrapper<const T*> span(const T* arr, int n) {
  return _iter_wrapper<const T*>{arr, arr + n};
}
template <class T, int N>
_iter_wrapper<const T*> span(const T (&arr)[N]) {
  return span(arr, N);
}
using namespace std;
using namespace rel_ops;
using ll = long long;
using ull = unsigned long long;
using Vi = vector<int>;
using Vll = vector<ll>;
using Vull = vector<ull>;
using Pii = pair<int, int>;
template <class T, class V>
auto operator<<(T& out, V val) -> decltype(val.print(0), out) {
  out << "{";
  val.print();
  return out << "}";
}
template <class T, class V>
auto operator<<(T& out, V val) -> decltype(get<1>(val), out) {
  return out << "(" << val.first << ", " << val.second << ")";
}
template <class T, class V>
auto operator<<(T& out, V val) -> decltype((val).begin(), (val).end(), out) {
  out << "[";
  bool comma = false;
  for (auto elem : val) {
    if (comma) out << ", ";
    out << elem;
    comma = true;
  }
  return out << "]";
}
void DD(...) {}
template <class T, class... S>
void DD(const char* format, T elem, S... rest) {
  int braces = 0;
  while (*format && (braces > 0 || *format != ',')) {
    if (*format == '(' || *format == '[' || *format == '{' || *format == '<') {
      braces++;
    }
    if (*format == ')' || *format == ']' || *format == '}' || *format == '>')
      braces--;
    cerr << *format++;
  }
  cerr << ": " << elem << *format++;
  DD(format, rest...);
}
template <class... T>
void _printDebug(int line, const char* format, T... elems) {
  cerr << '<';
  if (line < 10) cerr << '0';
  if (line < 100) cerr << '0';
  cerr << line << "> ";
  DD(format, elems...);
  cerr << endl;
}
void run();
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  run();
  return 0;
}
void transpose64(array<ull, 64>& M) {
  for (ull i = 0; i < 64; i += 1 * 2)
    for (ull j = i; j < i + 1; j++) {
      ull a = (M[j] >> 1) & 0x5555555555555555;
      ull b = (M[j + 1] << 1) & 0xAAAAAAAAAAAAAAAA;
      M[j] = (M[j] & 0x5555555555555555) | b;
      M[j + 1] = (M[j + 1] & 0xAAAAAAAAAAAAAAAA) | a;
    };
  for (ull i = 0; i < 64; i += 2 * 2)
    for (ull j = i; j < i + 2; j++) {
      ull a = (M[j] >> 2) & 0x3333333333333333;
      ull b = (M[j + 2] << 2) & 0xCCCCCCCCCCCCCCCC;
      M[j] = (M[j] & 0x3333333333333333) | b;
      M[j + 2] = (M[j + 2] & 0xCCCCCCCCCCCCCCCC) | a;
    };
  for (ull i = 0; i < 64; i += 4 * 2)
    for (ull j = i; j < i + 4; j++) {
      ull a = (M[j] >> 4) & 0xF0F0F0F0F0F0F0F;
      ull b = (M[j + 4] << 4) & 0xF0F0F0F0F0F0F0F0;
      M[j] = (M[j] & 0xF0F0F0F0F0F0F0F) | b;
      M[j + 4] = (M[j + 4] & 0xF0F0F0F0F0F0F0F0) | a;
    };
  for (ull i = 0; i < 64; i += 8 * 2)
    for (ull j = i; j < i + 8; j++) {
      ull a = (M[j] >> 8) & 0xFF00FF00FF00FF;
      ull b = (M[j + 8] << 8) & 0xFF00FF00FF00FF00;
      M[j] = (M[j] & 0xFF00FF00FF00FF) | b;
      M[j + 8] = (M[j + 8] & 0xFF00FF00FF00FF00) | a;
    };
  for (ull i = 0; i < 64; i += 16 * 2)
    for (ull j = i; j < i + 16; j++) {
      ull a = (M[j] >> 16) & 0xFFFF0000FFFF;
      ull b = (M[j + 16] << 16) & 0xFFFF0000FFFF0000;
      M[j] = (M[j] & 0xFFFF0000FFFF) | b;
      M[j + 16] = (M[j + 16] & 0xFFFF0000FFFF0000) | a;
    };
  for (ull i = 0; i < 64; i += 32 * 2)
    for (ull j = i; j < i + 32; j++) {
      ull a = (M[j] >> 32) & 0xFFFFFFFF;
      ull b = (M[j + 32] << 32) & 0xFFFFFFFF00000000;
      M[j] = (M[j] & 0xFFFFFFFF) | b;
      M[j + 32] = (M[j + 32] & 0xFFFFFFFF00000000) | a;
    };
}
struct DenseGraph {
  Vull M, marked;
  int n, stride;
  void init(int k) {
    n = k;
    stride = (k + 63) >> 6;
    M.resize(n * stride);
    clearVisited();
  }
  ull* edges(int i) { return &M[i * stride]; }
  bool hasEdge(int i, int j) { return (edges(i)[j >> 6] >> (j & 63)) & 1; }
  void addEdge(int i, int j) { edges(i)[j >> 6] |= 1ull << (j & 63); }
  void delEdge(int i, int j) { edges(i)[j >> 6] &= ~(1ull << (j & 63)); }
  void clearVisited() { marked.assign(stride, -1); }
  void visit(int i) { marked[i >> 6] &= ~(1ull << (i & 63)); }
  bool isVisited(int i) { return ~marked[i >> 6] & (1ull << (i & 63)); }
  template <class T>
  void dfsStep(int i, T func) {
    ull* E = edges(i);
    for (int w = 0; w < stride;) {
      ull first = E[w] & marked[w];
      if (first)
        func((w << 6) | __builtin_ctzll(first));
      else
        w++;
    }
  }
};
struct PathSet {
  map<int, ull> masks;
  bool get(int i) { return (masks[i >> 6] >> (i & 63)) & 1; }
  void insert(int i) { masks[i >> 6] |= 1ull << (i & 63); }
  bool xorIt(int i) {
    ull& mask = masks[i >> 6];
    i &= 63;
    mask ^= 1ull << i;
    return (mask >> i) & 1;
  }
  template <class T>
  void forEach(T func) {
    for (auto& mask : (masks)) {
      int offset = mask.first << 6;
      ull first = mask.second;
      while (first) {
        int bit = __builtin_ctzll(first);
        func(offset | bit);
        first &= ~(1ull << bit);
      }
    }
  }
};
struct Vert {
  Vi edges;
  PathSet paths;
  bool visited{false};
};
int n, m, nVars;
vector<Vert> tree;
DenseGraph sat;
stack<int> postOrder;
vector<int> vars;
void dfsCrossing(int i) {
  auto& cur = tree[i].paths;
  tree[i].visited = true;
  unordered_set<int> free;
  cur.forEach([&cur, &free](int path) { free.insert(path); });
  for (auto& e : (tree[i].edges)) {
    if (tree[e].visited) continue;
    dfsCrossing(e);
    auto& child = tree[e].paths;
    if (int((child.masks).size()) > int((cur.masks).size())) swap(cur, child);
    child.forEach([&cur, &free](int path) {
      if (cur.xorIt(path)) free.insert(path);
    });
  }
  for (auto& path : (free))
    if (cur.get(path)) {
      ull* edges = sat.edges(nVars + path);
      for (auto& mask : (cur.masks)) edges[mask.first] |= mask.second;
    }
}
int neg(int i) { return i < nVars ? i + nVars : i - nVars; }
bool tryAssign(int i, int val) {
  if (i < nVars) {
    if (vars[i]) return false;
    vars[i] = -val;
  } else {
    if (vars[i - nVars]) return false;
    vars[i - nVars] = val;
  }
  return true;
}
void dfsPostorder(int i) {
  sat.visit(i);
  sat.dfsStep(i, dfsPostorder);
  postOrder.push(i);
}
void dfsAssign(int i, bool first) {
  sat.visit(i);
  if (!tryAssign(i, 1)) {
    if (first) return;
    cout << "NO" << endl;
    exit(0);
  }
  sat.dfsStep(i, [](int j) { dfsAssign(j, false); });
}
void run() {
  cin >> n;
  tree.resize(n);
  for (int i = (1); i < (n); i++) {
    int a, b;
    cin >> a >> b;
    tree[a - 1].edges.push_back(b - 1);
    tree[b - 1].edges.push_back(a - 1);
  }
  cin >> m;
  for (int i = (0); i < (m); i++)
    for (int j = (0); j < (2); j++) {
      int a, b;
      cin >> a >> b;
      tree[a - 1].paths.insert(i * 2 + j);
      tree[b - 1].paths.insert(i * 2 + j);
    }
  nVars = m * 2;
  sat.init(nVars * 2);
  dfsCrossing(0);
  for (int i = (0); i < (nVars); i++) sat.delEdge(nVars + i, i);
  array<ull, 64> block1, block2;
  for (int i = 0; i * 64 < nVars; i++) {
    for (int j = 0; j * 64 < nVars; j++) {
      for (int second = (0); second < (64); second++) {
        int row1 = nVars + i * 64 + second, row2 = nVars + j * 64 + second;
        block1[second] = (row1 < sat.n ? sat.edges(row1)[j] : 0);
        block2[second] = (row2 < sat.n ? sat.edges(row2)[i] : 0);
      }
      transpose64(block1);
      transpose64(block2);
      for (int second = (0); second < (64); second++) {
        int row1 = nVars + i * 64 + second, row2 = nVars + j * 64 + second;
        if (row1 < sat.n) sat.edges(row1)[j] |= block2[second];
        if (row2 < sat.n) sat.edges(row2)[i] |= block1[second];
      }
    }
  }
  for (int i = (0); i < (m); i++) {
    int a = i * 2, b = i * 2 + 1;
    sat.addEdge(a, nVars + b);
    sat.addEdge(b, nVars + a);
    sat.addEdge(nVars + a, b);
    sat.addEdge(nVars + b, a);
  }
  for (int i = (0); i < (sat.n); i++)
    if (!sat.isVisited(i)) dfsPostorder(i);
  sat.clearVisited();
  vars.resize(nVars);
  while (!postOrder.empty()) {
    int i = postOrder.top();
    postOrder.pop();
    if (!sat.isVisited(i)) dfsAssign(neg(i), true);
  }
  cout << "YES\n";
  for (int i = (0); i < (m); i++) {
    cout << (vars[i * 2] == 1 ? 1 : 2) << '\n';
  }
}