Problem: To add insult to injury, the zombies have taken all but two drawings from Heidi! Please help her recover the Tree of Life from only these two drawings.

Input

The input format is the same as in the medium version, except that now the bound on n is 2 ≤ n ≤ 1000 and that k = 2.

Output

The same as in the medium version.

Example

Input

1
9 2
6
4 3
5 4
6 1
8 6
8 2
7 1
5
8 6
8 7
8 1
7 3
5 1


Output

YES
2 1
3 1
5 4
6 5
7 6
8 5
9 8
1 4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1010, MaxM = 2010;
const unsigned long long base = 300007, mod = 100000000000007ll;
unsigned long long rand_val[MaxN];
class Graph {
 public:
  int en[MaxN], next[MaxM], to[MaxM], tot;
  int lab[MaxN];
  void add_edge(int x, int y) {
    next[++tot] = en[x];
    en[x] = tot;
    to[tot] = y;
  }
  void clear() {
    memset(en, 0, sizeof en);
    tot = 0;
    memset(lab, 0, sizeof lab);
  }
} Gu, Gv;
struct Status {
  int ker;
  vector<pair<unsigned long long, int> > u, v;
};
vector<Status> Su, Sv;
vector<pair<int, int> > ans;
vector<int> stk;
int n, total;
int vis[MaxN], done[MaxN], v_time;
bool read_graph(Graph &G) {
  int m;
  scanf("%d", &m);
  map<int, int> hash;
  int total = 0;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    if (!hash.count(u)) hash[u] = ++total;
    if (!hash.count(v)) hash[v] = ++total;
    u = hash[u];
    v = hash[v];
    G.add_edge(u, v);
    G.add_edge(v, u);
  }
  if (total == n) return 1;
  return 0;
}
int size[MaxN], mx[MaxN];
int dfs_size(Graph &G, int now) {
  vis[now] = v_time;
  size[now] = 1;
  mx[now] = 0;
  stk.push_back(now);
  for (int i = G.en[now]; i; i = G.next[i])
    if (vis[G.to[i]] != v_time) {
      int tmp = dfs_size(G, G.to[i]);
      size[now] += tmp;
      mx[now] = max(mx[now], tmp);
    }
  return size[now];
}
pair<int, int> get_gra(Graph &G, int root, int u) {
  ++v_time;
  vis[u] = v_time;
  stk.clear();
  int sz = dfs_size(G, root);
  pair<int, int> ret(0, 0);
  int mn = sz;
  for (auto i : stk) {
    mx[i] = max(mx[i], sz - size[i]);
    mn = min(mn, mx[i]);
  }
  for (auto i : stk)
    if (mx[i] == mn) {
      if (ret.first == 0)
        ret.first = i;
      else
        ret.second = i;
    }
  return ret;
}
unsigned long long vec_hash(vector<unsigned long long> &s) {
  sort(s.begin(), s.end());
  unsigned long long ret = 0;
  for (unsigned int i = 0; i < s.size(); ++i)
    ret = ((ret * base + s[i]) ^ (s[i] * 2333 + rand_val[i])) % mod;
  return ret;
}
unsigned long long dfs_hash(Graph &G, int now) {
  vis[now] = v_time;
  done[now] = 1;
  vector<unsigned long long> v;
  for (int i = G.en[now]; i; i = G.next[i])
    if (v_time != vis[G.to[i]]) v.push_back(dfs_hash(G, G.to[i]));
  v.push_back(0);
  return vec_hash(v);
}
unsigned long long get_hash(Graph &G, int root, int u = 0) {
  pair<int, int> gra = get_gra(G, root, u);
  if (gra.second == 0) {
    ++v_time;
    vis[u] = v_time;
    return dfs_hash(G, gra.first);
  } else {
    vector<unsigned long long> v;
    ++v_time;
    vis[u] = v_time;
    vis[gra.second] = vis[gra.first] = v_time;
    v.push_back(dfs_hash(G, gra.first));
    v.push_back(dfs_hash(G, gra.second));
    v.push_back(base);
    return vec_hash(v);
  }
  return 0;
}
int relabel(Graph &G, int now, int flag = 0) {
  if (flag) stk.push_back(now);
  vis[now] = v_time;
  G.lab[now] = ++total;
  for (int i = G.en[now]; i; i = G.next[i])
    if (vis[G.to[i]] != v_time)
      ans.push_back(make_pair(G.lab[now], relabel(G, G.to[i], flag)));
  return G.lab[now];
}
pair<unsigned long long, int> set_xor(
    vector<pair<unsigned long long, int> > &u,
    vector<pair<unsigned long long, int> > &v) {
  if (u.size() < v.size() || u.size() > v.size() + 1) return make_pair(0, -1);
  multiset<unsigned long long> s;
  pair<unsigned long long, int> ret(0, 0);
  for (auto i : v) s.insert(i.first);
  for (auto i : u) {
    auto t = s.find(i.first);
    if (t == s.end()) {
      if (ret.second != 0)
        return make_pair(0, -1);
      else
        ret = i;
    } else
      s.erase(t);
  }
  if (u.size() == v.size() && ret.second != 0) return make_pair(0, -1);
  return ret;
}
bool check(Status Su, Status Sv) {
  pair<unsigned long long, int> com_u, com_v;
  com_u = set_xor(Su.u, Sv.v);
  com_v = set_xor(Sv.u, Su.v);
  if (com_u.second == -1 || com_v.second == -1 || com_u.first != com_v.first)
    return 0;
  if ((com_u.second == 0) ^ (com_v.second == 0)) return 0;
  total = 2;
  int u = Su.ker, v = Sv.ker;
  for (int i = Gu.en[u]; i; i = Gu.next[i])
    if (Gu.to[i] != com_u.second) {
      ++v_time;
      vis[Su.ker] = v_time;
      ans.push_back(make_pair(1, relabel(Gu, Gu.to[i])));
    }
  for (int i = Gv.en[v]; i; i = Gv.next[i])
    if (Gv.to[i] != com_v.second) {
      ++v_time;
      vis[Sv.ker] = v_time;
      ans.push_back(make_pair(2, relabel(Gv, Gv.to[i])));
    }
  if (com_u.second == 0)
    ans.push_back(make_pair(1, 2));
  else {
    stk.clear();
    ++v_time;
    vis[Su.ker] = v_time;
    ans.push_back(make_pair(1, relabel(Gu, com_u.second, 1)));
    ++v_time;
    vis[Sv.ker] = v_time;
    unsigned long long hv = dfs_hash(Gv, com_v.second);
    for (auto i : stk) {
      ++v_time;
      vis[Su.ker] = v_time;
      unsigned long long tmp = dfs_hash(Gu, i);
      if (tmp == hv) {
        ans.push_back(make_pair(2, Gu.lab[i]));
        break;
      }
    }
  }
  return 1;
}
void work(Graph &G, vector<Status> &S) {
  for (int u = 1; u < n; ++u) {
    Status now;
    now.ker = u;
    memset(done, 0, sizeof done);
    done[u] = 1;
    for (int i = G.en[u]; i; i = G.next[i])
      now.u.push_back(make_pair(get_hash(G, G.to[i], u), G.to[i]));
    for (int i = 1; i < n; ++i)
      if (!done[i]) now.v.push_back(make_pair(get_hash(G, i, u), i));
    S.push_back(now);
  }
}
void solve() {
  ans.clear();
  Gu.clear();
  Gv.clear();
  Su.clear();
  Sv.clear();
  scanf("%d%*d", &n);
  bool flag = 0;
  flag |= read_graph(Gu);
  flag |= read_graph(Gv);
  for (int i = 0; i <= n; ++i)
    rand_val[i] = ((unsigned long long)rand() << 15) ^ rand();
  if (flag) {
    puts("NO");
    return;
  }
  work(Gu, Su);
  work(Gv, Sv);
  for (auto i : Su)
    for (auto j : Sv)
      if (check(i, j)) {
        assert(int(ans.size()) == n - 1);
        puts("YES");
        for (auto e : ans) printf("%d %d\n", e.first, e.second);
        return;
      }
  puts("NO");
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) solve();
  return 0;
}