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>
using namespace std;
using int64 = long long int;
struct Path {
  int u, v;
  int lca;
  int index;
  bool is_first;
};
class Graph {
 public:
  void AC(int u, int v) {
    AE(u, v, &e_);
    AE(v, u, &re_);
    AE(v ^ 1, u ^ 1, &e_);
    AE(u ^ 1, v ^ 1, &re_);
  }
  vector<bool> Solve() {
    int n = e_.size();
    c_.assign(n, -1);
    l_.clear();
    l_.reserve(n);
    for (int y = 0; y < n; ++y) {
      if (c_[y] == -1) {
        Dfs(y);
      }
    }
    int cur_x = 0;
    fill(c_.begin(), c_.end(), -1);
    for (int index = n - 1; index >= 0; --index) {
      int y = l_[index];
      if (c_[y] == -1) {
        Dfs2(y, cur_x++);
      }
    }
    vector<bool> ouc(n / 2);
    for (int i = 0; i < n / 2; ++i) {
      if (c_[2 * i] == c_[2 * i + 1]) {
        ouc.clear();
        return ouc;
      }
      ouc[i] = (c_[2 * i] > c_[2 * i + 1]);
    }
    return ouc;
  }

 private:
  static void AE(int u, int v, vector<vector<int>>* edges) {
    while (edges->size() <= static_cast<size_t>(u | 1)) {
      edges->emplace_back();
    }
    (*edges)[u].push_back(v);
  }
  void Dfs(int y) {
    c_[y] = 1;
    for (int other : e_[y]) {
      if (c_[other] == -1) {
        Dfs(other);
      }
    }
    l_.push_back(y);
  }
  void Dfs2(int y, int x) {
    c_[y] = x;
    for (int other : re_[y]) {
      if (c_[other] == -1) {
        Dfs2(other, x);
      }
    }
  }
  vector<vector<int>> e_;
  vector<vector<int>> re_;
  vector<int> c_;
  vector<int> l_;
};
class Tree {
 public:
  explicit Tree(int n) : e_(n) {}
  void AE(int u, int v) {
    e_[u].push_back(v);
    e_[v].push_back(u);
  }
  void Build() {
    et_.assign(e_.size(), 0);
    et_to_y_.assign(2 * e_.size() - 1, 0);
    ls_.reserve(2 * e_.size() - 1);
    Dfs(0, -1);
    BuildTree();
    rp_.assign(e_.size(), {});
    pee_.assign(e_.size(), {});
  }
  int gl(int u, int v) {
    size_t first = (ab_.size() >> 1) + et_[u];
    size_t last = (ab_.size() >> 1) + et_[v];
    if (first > last) {
      swap(first, last);
    }
    size_t lca = ab_[first++];
    while (first <= last) {
      if ((first & 1) != 0) {
        lca = min(lca, ab_[first++]);
      }
      if ((last & 1) == 0) {
        lca = min(lca, ab_[last--]);
      }
      first >>= 1;
      last >>= 1;
    }
    return et_to_y_[lca];
  }
  void AddPath(Path& path) {
    int index = 2 * path.index + (path.is_first ? 0 : 1);
    rp_[path.lca].push_back(index);
    if (path.u != path.lca) {
      pee_[path.u].push_back(index);
    }
    if (path.v != path.lca) {
      pee_[path.v].push_back(index);
    }
  }
  vector<bool> BS(int num_ants) {
    num_ants_ = num_ants;
    for (int i = 0; i < 2 * num_ants; ++i) {
      MakeLeafy(i);
    }
    DfsSat(0);
    vector<bool> values = g_.Solve();
    if (!values.empty()) {
      values.resize(num_ants_);
    }
    return values;
  }

 private:
  struct y {
    int l;
    int r;
    bool xx;
  };
  void Dfs(int y, int parent) {
    size_t current_time = ls_.size();
    et_[y] = current_time;
    et_to_y_[current_time] = y;
    ls_.push_back(current_time);
    for (size_t i = 0; i < e_[y].size(); ++i) {
      int child = e_[y][i];
      if (child != parent) {
        Dfs(child, y);
        ls_.push_back(current_time);
      } else {
        swap(e_[y][i--], e_[y].back());
        e_[y].resize(e_[y].size() - 1);
      }
    }
  }
  void BuildTree() {
    size_t n = ls_.size();
    ab_.assign(2 * n, 0);
    for (size_t i = 0; i < n; ++i) {
      ab_[i + n] = ls_[i];
    }
    for (size_t i = n - 1; i > 0; --i) {
      ab_[i] = min(ab_[i << 1], ab_[(i << 1) ^ 1]);
    }
  }
  int DfsSat(int y) {
    int ouc = -1;
    for (int child : e_[y]) {
      ouc = He(ouc, DfsSat(child), 0, 2 * num_ants_);
    }
    for (int path_index : rp_[y]) {
      ouc = Update(ouc, 0, 2 * num_ants_, path_index, true);
    }
    for (int path_index : pee_[y]) {
      ouc = Update(ouc, 0, 2 * num_ants_, path_index, false);
    }
    ACs(ouc);
    return ouc;
  }
  int He(int ur1, int ur2, int start, int limit) {
    if (ur1 == -1) {
      return ur2;
    } else if (ur2 == -1) {
      return ur1;
    }
    if (start + 1 == limit) {
      return ur1;
    }
    int middle = (start + limit) / 2;
    return MIy(He(ys_[ur1].l, ys_[ur2].l, start, middle),
               He(ys_[ur1].r, ys_[ur2].r, middle, limit));
  }
  int Update(int ur, int start, int limit, int index, bool doit) {
    if (start + 1 == limit) {
      return doit ? -1 : GetLeafy(index);
    }
    int l = (ur == -1 ? -1 : ys_[ur].l);
    int r = (ur == -1 ? -1 : ys_[ur].r);
    int middle = (start + limit) / 2;
    if (index < middle) {
      return MIy(Update(l, start, middle, index, doit), r);
    } else {
      return MIy(l, Update(r, middle, limit, index, doit));
    }
  }
  int MIy(int l, int r) {
    if (l == -1 && r == -1) {
      return -1;
    }
    int id = ys_.size();
    y y;
    y.l = l;
    y.r = r;
    y.xx = false;
    ys_.push_back(y);
    return id;
  }
  void ACs(int id) {
    if (id == -1 || ys_[id].xx) {
      return;
    }
    ys_[id].xx = true;
    if (ys_[id].l != -1) {
      g_.AC(2 * (num_ants_ + ys_[id].l), 2 * (num_ants_ + id));
    }
    if (ys_[id].r != -1) {
      g_.AC(2 * (num_ants_ + ys_[id].r), 2 * (num_ants_ + id));
    }
    if (ys_[id].l != -1 && ys_[id].r != -1) {
      g_.AC(2 * (num_ants_ + ys_[id].l), 2 * (num_ants_ + ys_[id].r) + 1);
    }
    ACs(ys_[id].l);
    ACs(ys_[id].r);
  }
  int MakeLeafy(int index) {
    int id = ys_.size();
    y y;
    y.l = y.r = -1;
    y.xx = true;
    ys_.push_back(y);
    g_.AC(index, 2 * (num_ants_ + index));
    return id;
  }
  int GetLeafy(int index) { return index; }
  vector<vector<int>> e_;
  vector<size_t> et_;
  vector<int> et_to_y_;
  vector<size_t> ls_;
  vector<size_t> ab_;
  int num_ants_;
  vector<vector<int>> rp_;
  vector<vector<int>> pee_;
  vector<y> ys_;
  Graph g_;
};
void solve() {
  int n;
  scanf("%d", &n);
  Tree t(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    t.AE(u - 1, v - 1);
  }
  t.Build();
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < 2; ++j) {
      Path path;
      scanf("%d %d", &path.u, &path.v);
      path.lca = t.gl(--path.u, --path.v);
      path.index = i;
      path.is_first = (j == 0);
      t.AddPath(path);
    }
  }
  vector<bool> answer = t.BS(m);
  if (!answer.empty()) {
    cout << "YES\n";
    for (int i = 0; i < m; ++i) {
      cout << (answer[i] ? "1" : "2") << "\n";
    }
  } else {
    cout << "NO\n";
  }
}
int main() {
  solve();
  return 0;
}