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;
namespace whatever {
int readu() {
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  int value = ch - '0';
  ch = getchar();
  while (isdigit(ch)) {
    value = value * 10 + ch - '0';
    ch = getchar();
  }
  return value;
}
void writeu(int n) {
  if (n < 10)
    putchar(n + '0');
  else {
    writeu(n / 10);
    putchar(n % 10 + '0');
  }
}
const size_t node_size = 16 * 10000 * 4 * 3;
const size_t graph_size = (10000 * 2 + node_size) * 2;
namespace graph {
int vertex_cnt;
vector<int> adj[graph_size];
void connect(int a, int i, int b, int j) {
  assert(a * 2 < vertex_cnt);
  assert(b * 2 < vertex_cnt);
  adj[a * 2 + i].push_back(b * 2 + j);
  adj[b * 2 + 1 - j].push_back(a * 2 + 1 - i);
}
int dfn[graph_size];
int low[graph_size];
int dfs_time;
int stack[graph_size];
bool in_stack[graph_size];
int top;
int scc[graph_size];
int scc_cnt;
void dfs(int cur) {
  dfn[cur] = low[cur] = ++dfs_time;
  stack[top++] = cur;
  in_stack[cur] = true;
  for (int to : adj[cur])
    if (dfn[to] == 0) {
      dfs(to);
      low[cur] = min(low[cur], low[to]);
    } else if (in_stack[to])
      low[cur] = min(low[cur], dfn[to]);
  if (low[cur] == dfn[cur]) {
    ++scc_cnt;
    do {
      --top;
      in_stack[stack[top]] = false;
      scc[stack[top]] = scc_cnt;
    } while (stack[top] != cur);
  }
}
}  // namespace graph
namespace segment_tree {
struct node_type {
  node_type *left;
  node_type *right;
  int index;
};
const int s = (1 << 15);
node_type node[node_size];
int node_cnt;
node_type *allocate() {
  node[node_cnt].index = graph::vertex_cnt / 2;
  graph::vertex_cnt += 2;
  return &node[node_cnt++];
}
node_type *make(int value) {
  node_type *root = allocate();
  node_type *cur = root;
  for (int bit = (s >> 1); bit != 0; bit >>= 1)
    if (value & bit) {
      cur->right = allocate();
      graph::connect(cur->index, 1, cur->right->index, 1);
      cur = cur->right;
    } else {
      cur->left = allocate();
      graph::connect(cur->index, 1, cur->left->index, 1);
      cur = cur->left;
    }
  graph::connect(cur->index, 1, value, 1);
  return root;
}
node_type *merge(node_type *a, node_type *b) {
  if (!a) return b;
  if (!b) return a;
  node_type *result = allocate();
  result->left = merge(a->left, b->left);
  result->right = merge(a->right, b->right);
  if (result->left) graph::connect(result->index, 1, result->left->index, 1);
  if (result->right) graph::connect(result->index, 1, result->right->index, 1);
  if (result->left && result->right)
    graph::connect(result->left->index, 0, result->right->index, 1);
  return result;
}
node_type *erase(node_type *prev, int value) {
  node_type *root = allocate();
  node_type *cur = root;
  for (int bit = (s >> 1); bit != 0; bit >>= 1)
    if (value & bit) {
      assert(prev);
      cur->right = allocate();
      graph::connect(cur->index, 1, cur->right->index, 1);
      cur->left = prev->left;
      if (cur->left) {
        graph::connect(cur->index, 1, cur->left->index, 1);
        graph::connect(cur->left->index, 0, cur->right->index, 1);
      }
      cur = cur->right;
      prev = prev->right;
    } else {
      assert(prev);
      cur->left = allocate();
      graph::connect(cur->index, 1, cur->left->index, 1);
      cur->right = prev->right;
      if (cur->right) {
        graph::connect(cur->index, 1, cur->right->index, 1);
        graph::connect(cur->right->index, 0, cur->left->index, 1);
      }
      cur = cur->left;
      prev = prev->left;
    }
  return root;
}
}  // namespace segment_tree
namespace tree {
vector<int> adj[100000 + 1];
int father[100000 + 1];
int size[100000 + 1];
int child[100000 + 1];
int depth[100000 + 1];
void dfs1(int cur) {
  size[cur] = 1;
  for (int to : adj[cur])
    if (to != father[cur]) {
      father[to] = cur;
      depth[to] = depth[cur] + 1;
      dfs1(to);
      size[cur] += size[to];
      if (size[child[cur]] < size[to]) child[cur] = to;
    }
}
int dfn[100000 + 1];
int order[100000];
int dfs_time;
int top[100000 + 1];
void dfs2(int cur) {
  order[dfs_time] = cur;
  dfn[cur] = dfs_time++;
  if (child[cur] != 0) {
    top[child[cur]] = top[cur];
    dfs2(child[cur]);
  }
  for (int to : adj[cur])
    if (to != father[cur] && to != child[cur]) {
      top[to] = to;
      dfs2(to);
    }
}
int lca(int a, int b) {
  while (top[a] != top[b])
    if (depth[top[a]] < depth[top[b]])
      b = father[top[b]];
    else
      a = father[top[a]];
  if (depth[a] < depth[b])
    return a;
  else
    return b;
}
int ancestor(int a, int level) {
  while (level > depth[a] - depth[top[a]]) {
    level -= depth[a] - depth[father[top[a]]];
    a = father[top[a]];
  }
  return order[dfn[a] - level];
}
segment_tree::node_type *root[100000 + 1];
vector<int> insert[100000 + 1];
vector<int> erase[100000 + 1];
void dfs3(int cur) {
  for (int value : insert[cur])
    root[cur] = merge(root[cur], segment_tree::make(value));
  for (int to : adj[cur])
    if (to != father[cur]) {
      dfs3(to);
      root[cur] = merge(root[cur], root[to]);
    }
  for (int value : erase[cur])
    root[cur] = segment_tree::erase(root[cur], value);
}
}  // namespace tree
void run() {
  int n = readu();
  for (int i = 1; i < n; ++i) {
    int u = readu();
    int v = readu();
    tree::adj[u].push_back(v);
    tree::adj[v].push_back(u);
  }
  tree::father[1] = 0;
  tree::depth[1] = 0;
  tree::dfs1(1);
  tree::top[1] = 1;
  tree::dfs2(1);
  int m = readu();
  static int index[10000];
  for (int i = 0; i < m; ++i) {
    index[i] = graph::vertex_cnt;
    graph::vertex_cnt += 4;
    graph::connect(index[i] / 2, 1, index[i] / 2 + 1, 0);
    for (int j = 0; j < 2; ++j) {
      int a = readu();
      int b = readu();
      int l = tree::lca(a, b);
      if (a != l) {
        tree::insert[a].push_back(index[i] / 2 + j);
        tree::erase[tree::ancestor(a, tree::depth[a] - tree::depth[l] - 1)]
            .push_back(index[i] / 2 + j);
      }
      if (b != l) {
        tree::insert[b].push_back(index[i] / 2 + j);
        tree::erase[tree::ancestor(b, tree::depth[b] - tree::depth[l] - 1)]
            .push_back(index[i] / 2 + j);
      }
    }
  }
  assert(graph::vertex_cnt == m * 2 * 2);
  tree::dfs3(1);
  cerr << "segment_tree::node_cnt: " << segment_tree::node_cnt << endl;
  assert(graph::vertex_cnt == (m * 2 + segment_tree::node_cnt) * 2);
  for (int i = 0; i < graph::vertex_cnt; ++i)
    if (graph::dfn[i] == 0) graph::dfs(i);
  cerr << "graph::scc_cnt: " << graph::scc_cnt << endl;
  bool ok = true;
  for (int i = 0; i < graph::vertex_cnt; i += 2)
    if (graph::scc[i] == graph::scc[i + 1]) ok = false;
  if (ok) {
    puts("YES");
    for (int i = 0; i < m; ++i) {
      if (graph::scc[index[i]] < graph::scc[index[i] + 1])
        putchar('1');
      else {
        assert(graph::scc[index[i] + 2] < graph::scc[index[i] + 3]);
        putchar('2');
      }
      putchar('\n');
    }
  } else {
    puts("NO");
  }
}
}  // namespace whatever
int main() { whatever::run(); }