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;
struct SCC {
  int V;
  vector<vector<int>> adj;
  vector<int> discovery, low_link;
  int index;
  int S;
  vector<int> stack;
  vector<bool> on_stack;
  vector<vector<int>> components;
  vector<int> which_component;
  SCC(int v = 0) {
    if (v > 0) init(v);
  }
  SCC(const vector<vector<int>> &_adj) { init(_adj); }
  void init(int v) {
    V = v;
    adj.assign(V, vector<int>());
  }
  void init(const vector<vector<int>> &_adj) {
    adj = _adj;
    V = adj.size();
  }
  void add_edge(int a, int b) { adj[a].push_back(b); }
  void dfs(int node) {
    discovery[node] = low_link[node] = index++;
    stack[S++] = node;
    on_stack[node] = true;
    for (int neighbor : adj[node])
      if (discovery[neighbor] == -1) {
        dfs(neighbor);
        low_link[node] = min(low_link[node], low_link[neighbor]);
      } else if (on_stack[neighbor]) {
        low_link[node] = min(low_link[node], discovery[neighbor]);
      }
    if (low_link[node] == discovery[node]) {
      components.emplace_back();
      vector<int> &component = components.back();
      int x;
      do {
        assert(S > 0);
        x = stack[--S];
        on_stack[x] = false;
        component.push_back(x);
        which_component[x] = components.size() - 1;
      } while (x != node);
    }
  }
  void build() {
    discovery.assign(V, -1);
    low_link.assign(V, -1);
    which_component.assign(V, -1);
    S = 0;
    stack.resize(V);
    on_stack.assign(V, false);
    index = 0;
    components.clear();
    for (int i = 0; i < V; i++)
      if (discovery[i] == -1) dfs(i);
  }
};
struct two_sat {
  int n;
  vector<vector<int>> adj;
  vector<bool> assignment;
  two_sat() : n(0) {}
  int inv(int var) { return var ^ 1; }
  int new_var() {
    adj.emplace_back();
    adj.emplace_back();
    return 2 * n++;
  }
  void implies(int a, int b) {
    adj[a].push_back(b);
    adj[inv(b)].push_back(inv(a));
  }
  void either(int a, int b) {
    adj[inv(a)].push_back(b);
    adj[inv(b)].push_back(a);
  }
  void set_value(int a) { adj[inv(a)].push_back(a); }
  int create_and(int a, int b) {
    if (a < 0 || b < 0) return max(a, b);
    int result = new_var();
    implies(result, a);
    implies(result, b);
    return result;
  }
  int create_or(int a, int b) {
    if (a < 0 || b < 0) return max(a, b);
    int result = new_var();
    implies(a, result);
    implies(b, result);
    return result;
  }
  int create_at_most_one(int a, int b) {
    if (a < 0 || b < 0) return max(a, b);
    either(inv(a), inv(b));
    return create_or(a, b);
  }
  template <typename T_iterable>
  int create_at_most_one(const T_iterable &vars) {
    int aux = -1;
    for (int var : vars) aux = create_at_most_one(aux, var);
    return aux;
  }
  bool solve() {
    SCC scc(adj);
    scc.build();
    for (int i = 0; i < n; i++)
      if (scc.which_component[2 * i] == scc.which_component[2 * i + 1])
        return false;
    assignment.resize(n);
    vector<bool> done(n, false);
    for (auto &component : scc.components)
      for (int x : component)
        if (!done[x / 2]) {
          done[x / 2] = true;
          assignment[x / 2] = x % 2 == 0;
        }
    return true;
  }
};
two_sat TS;
struct seg_tree {
  int tree_n;
  vector<vector<int>> tree;
  seg_tree(int n = 0) {
    tree_n = 0;
    if (n > 0) init(n);
  }
  void init(int n) {
    tree_n = 1;
    while (tree_n < n) tree_n *= 2;
    tree.assign(2 * tree_n, vector<int>());
  }
  bool empty() const { return tree_n == 0; }
  void add_path(int a, int b, int var) {
    for (a += tree_n, b += tree_n; a < b; a /= 2, b /= 2) {
      if (a & 1) tree[a++].push_back(var);
      if (b & 1) tree[--b].push_back(var);
    }
  }
  void build_implications(int position = 1, int parent_var = -1) {
    int my_var = TS.create_at_most_one(tree[position]);
    my_var = TS.create_at_most_one(parent_var, my_var);
    if (position >= tree_n) return;
    build_implications(2 * position, my_var);
    build_implications(2 * position + 1, my_var);
  }
};
struct heavy_light {
  int n;
  bool vertex_mode;
  vector<vector<int>> adj;
  vector<int> parent;
  vector<int> depth;
  vector<int> subtree_size;
  vector<int> chain_root;
  vector<int> chain_size;
  vector<seg_tree> chain_tree;
  heavy_light(int _n = 0, bool _vertex_mode = false) {
    if (_n > 0) init(_n, _vertex_mode);
  }
  void init(int _n, bool _vertex_mode) {
    n = _n;
    vertex_mode = _vertex_mode;
    adj.clear();
    adj.resize(n);
    parent.resize(n);
    depth.resize(n);
    subtree_size.resize(n);
    chain_root.resize(n);
    chain_size.assign(n, 0);
    chain_tree.clear();
    chain_tree.resize(n);
  }
  void add_edge(int a, int b) {
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  void dfs(int node, int par) {
    parent[node] = par;
    depth[node] = par == -1 ? 0 : depth[par] + 1;
    subtree_size[node] = 1;
    for (int neighbor : adj[node])
      if (neighbor != par) {
        dfs(neighbor, node);
        subtree_size[node] += subtree_size[neighbor];
      }
  }
  void chain_dfs(int node, bool heavy) {
    chain_root[node] = heavy ? chain_root[parent[node]] : node;
    chain_size[chain_root[node]]++;
    int biggest_subtree = 0;
    int heavy_child = -1;
    for (int neighbor : adj[node])
      if (neighbor != parent[node] &&
          subtree_size[neighbor] > biggest_subtree) {
        biggest_subtree = subtree_size[neighbor];
        heavy_child = neighbor;
      }
    for (int neighbor : adj[node])
      if (neighbor != parent[node])
        chain_dfs(neighbor, neighbor == heavy_child);
  }
  void build() {
    dfs(0, -1);
    chain_dfs(0, false);
    for (int i = 0; i < n; i++)
      if (chain_root[i] == i) chain_tree[i].init(chain_size[i]);
  }
  template <typename T_tree_op>
  void process_path(int u, int v, T_tree_op &&op) {
    while (chain_root[u] != chain_root[v]) {
      if (depth[chain_root[u]] > depth[chain_root[v]]) swap(u, v);
      int root = chain_root[v];
      op(chain_tree[root], 0, depth[v] - depth[root] + 1);
      v = parent[chain_root[v]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    int root = chain_root[v];
    op(chain_tree[root], depth[u] - depth[root] + (vertex_mode ? 0 : 1),
       depth[v] - depth[root] + 1);
  }
  void add_path(int u, int v, int var) {
    process_path(
        u, v, [&](seg_tree &tree, int a, int b) { tree.add_path(a, b, var); });
  }
  void build_all_implications() {
    for (seg_tree &tree : chain_tree)
      if (!tree.empty()) tree.build_implications();
  }
};
int main() {
  int N;
  scanf("%d", &N);
  heavy_light HLD(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--;
    v--;
    HLD.add_edge(u, v);
  }
  HLD.build();
  int M;
  scanf("%d", &M);
  vector<int> vars(M);
  for (int i = 0; i < M; i++) vars[i] = TS.new_var();
  for (int i = 0; i < M; i++) {
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    a--;
    b--;
    c--;
    d--;
    HLD.add_path(a, b, vars[i]);
    HLD.add_path(c, d, TS.inv(vars[i]));
  }
  HLD.build_all_implications();
  cerr << TS.n << " nodes" << endl;
  if (!TS.solve()) {
    puts("NO");
    return 0;
  }
  puts("YES");
  for (int i = 0; i < M; i++) puts(TS.assignment[i] ? "1" : "2");
}