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;
inline int read() {
  int sum = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch <= '9' && ch >= '0') sum = sum * 10 + ch - '0', ch = getchar();
  return sum;
}
int T;
int n, k;
const int ch1 = 29, ch2 = 31;
const int mod = 1e9 + 7;
struct Pair {
  int x;
  unsigned long long y;
  Pair(int x_ = 0, unsigned long long y_ = 0) : x(x_), y(y_) {}
  bool operator==(Pair s) const { return x == s.x && y == s.y; }
  bool operator<(Pair s) const { return x == s.x ? y < s.y : x < s.x; }
  Pair operator+(Pair s) const { return Pair((x + s.x) % mod, y + s.y); }
  Pair operator-(Pair s) const { return Pair((x - s.x + mod) % mod, y - s.y); }
  Pair operator*(Pair s) const { return Pair(1ll * x * s.x % mod, y * s.y); }
};
struct opt {
  Pair a, b, c;
  opt() {}
  bool operator<(opt s) const {
    if (a == s.a) {
      if (b == s.b)
        return c < s.c;
      else
        return b < s.b;
    } else
      return a < s.a;
  }
};
Pair poww[1010];
void pre() {
  Pair g = Pair(ch1, ch2);
  poww[0] = Pair(1, 1);
  for (int i = 1; i <= 1000; i++) poww[i] = poww[i - 1] * g;
}
Pair yuan() { return (poww[1] + Pair(212, 23)) * poww[1]; }
map<opt, pair<int, int> > As;
map<Pair, int> To;
pair<int, int> ANS[1010];
int tot;
int zhan[1010], oo;
struct Tu {
  int head[1010], last[1010 << 1], v[1010 << 1], p;
  bool vis[1010];
  int A, B, Sum;
  int Size[1010], mmax[1010];
  Pair ff[1010];
  void getsize(int a, int b, int c) {
    Size[a] = 1;
    mmax[a] = 0;
    for (int i = head[a]; i; i = last[i])
      if (v[i] != b && v[i] != c)
        getsize(v[i], a, c), Size[a] += Size[v[i]],
            mmax[a] = max(mmax[a], Size[v[i]]);
  }
  void getrt(int a, int b, int c) {
    mmax[a] = max(mmax[a], Sum - Size[a]);
    if (mmax[a] <= (Sum >> 1)) {
      if (!A)
        A = a;
      else
        B = a;
    }
    for (int i = head[a]; i; i = last[i])
      if (v[i] != b && v[i] != c) getrt(v[i], a, c);
  }
  Pair H(int a, int b, int c) {
    zhan[++oo] = a;
    vis[a] = 1;
    Pair uu = Pair(1, 1);
    for (int i = head[a]; i; i = last[i])
      if (v[i] != b && v[i] != c) {
        Pair A = H(v[i], a, c);
        uu = uu + A;
      }
    uu = uu * poww[Size[a]];
    uu = uu + Pair(212, 23);
    uu = uu * poww[1];
    return uu;
  }
  Pair gen(int a, int b, int c) {
    getsize(a, b, c);
    oo = 0;
    return H(a, b, c);
  }
  Pair suan(int w, int s) {
    A = 0, B = 0;
    getsize(w, s, s);
    Sum = Size[w];
    getrt(w, s, s);
    Pair L, R;
    if (A) L = gen(A, 0, s);
    if (B) R = gen(B, 0, s);
    if (L < R) swap(L, R);
    return L + (R * poww[1]);
  }
  void add(int a, int b) {
    v[++p] = b;
    last[p] = head[a];
    head[a] = p;
  }
  void reset() {
    memset(id, 0, sizeof(id));
    memset(vis, 0, sizeof(vis));
    memset(head, 0, sizeof(head));
    p = 0;
  }
  Pair st[1010];
  int num;
  void build() {
    for (int i = 1; i <= n; i++) {
      memset(vis, 0, sizeof(vis));
      num = 0;
      Pair ss, tt;
      for (int j = head[i]; j; j = last[j])
        st[++num] = suan(v[j], i), ss = ss + st[num], Z[num] = v[j];
      for (int j = 1; j <= n; j++)
        if (!vis[j] && j != i) tt = tt + suan(j, i);
      for (int j = 0; j <= num; j++) {
        opt AA;
        AA.a = ss - st[j], AA.b = st[j], AA.c = tt - yuan();
        As[AA] = make_pair(i, Z[j]);
      }
    }
  }
  int Z[1010];
  pair<int, int> find(int &gf, Pair &ww) {
    for (int i = 1; i <= n; i++) {
      memset(vis, 0, sizeof(vis));
      num = 0;
      Pair ss, tt;
      for (int j = head[i]; j; j = last[j])
        st[++num] = suan(v[j], i), ss = ss + st[num], Z[num] = v[j];
      for (int j = 1; j <= n; j++)
        if (!vis[j] && j != i) tt = tt + suan(j, i);
      for (int j = 0; j <= num; j++) {
        opt AA;
        AA.c = ss - st[j], AA.b = st[j], AA.a = tt - yuan();
        if (As.count(AA)) {
          gf = As[AA].second;
          ww = AA.b;
          return AA.b == Pair(0, 0) ? make_pair(As[AA].first, -i)
                                    : make_pair(As[AA].first, i);
        }
      }
    }
    return make_pair(-1, -1);
  }
  int id[1010];
  int cnt;
  void solve(int a, int b, int c) {
    if (!id[a]) id[a] = ++cnt;
    if (c) ANS[++tot] = make_pair(c, id[a]);
    vis[a] = 1;
    for (int i = head[a]; i; i = last[i])
      if (v[i] != b) solve(v[i], a, id[a]);
  }
} S[2];
int lky[1010], gh;
void solve() {
  As.clear();
  To.clear();
  S[0].reset(), S[1].reset();
  for (int i = 0; i < k; i++) {
    int m = read();
    for (int j = 1; j <= m; j++) {
      int l = read(), r = read();
      S[i].add(l, r);
      S[i].add(r, l);
    }
  }
  S[0].build();
  int from;
  Pair to;
  pair<int, int> gg = S[1].find(from, to);
  if (gg.first == -1) {
    cout << "NO\n";
    return;
  }
  int X = gg.first, Y = abs(gg.second);
  S[0].getsize(X, 0, 0);
  for (int i = S[0].head[X]; i; i = S[0].last[i]) {
    Pair AA = S[0].gen(S[0].v[i], X, X);
    To[AA]++;
  }
  memset(S[1].vis, 0, sizeof(S[1].vis));
  oo = 0;
  Pair Ss = S[1].H(Y, 0, 0);
  gh = oo, memcpy(lky, zhan, sizeof(zhan));
  tot = 0;
  S[1].cnt = 0;
  S[1].solve(Y, 0, 0);
  int rt = ++S[1].cnt;
  bool flag = 0;
  for (int i = 1; i <= n; i++)
    if (!S[1].vis[i]) {
      Pair ff = S[1].gen(i, 0, 0);
      if (!flag) {
        if (S[1].suan(i, 0) == yuan()) {
          flag = 1;
          for (int j = 1; j <= oo; j++) S[1].vis[zhan[j]] = 0;
          continue;
        }
      }
      if (To.count(ff) && To[ff]) {
        S[1].solve(i, 0, rt);
        To[ff]--;
      } else {
        for (int j = 1; j <= oo; j++) S[1].vis[zhan[j]] = 0;
      }
    }
  cout << "YES\n";
  if (gg.second > 0) {
    for (int i = 1; i <= gh; i++)
      if (lky[i] != Y) {
        Pair LL = S[1].suan(lky[i], Y);
        Pair RR = S[1].gen(lky[i], Y, Y);
        if (LL == to && RR == S[0].gen(from, X, X)) {
          ANS[++tot] = make_pair(rt, S[1].id[lky[i]]);
          break;
        }
      }
  } else
    ANS[++tot] = make_pair(rt, 1);
  for (int i = 1; i < n; i++)
    cout << ANS[i].first << " " << ANS[i].second << '\n';
}
int main() {
  pre();
  T = read();
  while (T--) {
    n = read(), k = read();
    solve();
  }
  return 0;
}