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 N = 1010, oo = 1000000000;
int i, j, k, n, m, Test, nm, ch, Fg, na, nb, ta, tb, tt, x, y, num, xx, yy, tx,
    ty, Txy, ans, px, py, tA, tB;
int f[N];
map<vector<int>, int> Map;
map<int, int> P;
struct edge {
  int s, n;
};
struct cc {
  int x, hs;
  bool operator<(const cc &n) const {
    if (hs == n.hs) return x < n.x;
    return hs < n.hs;
  }
};
struct dd {
  int x, y;
} Ans[N];
void R(int &x) {
  x = 0;
  ch = getchar();
  while (ch < '0' || '9' < ch) ch = getchar();
  while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
int getf(int x) {
  if (f[x] == x) return x;
  return f[x] = getf(f[x]);
}
struct forest {
  int i, j, k, m, En, size, rt1, rt2, mi1, mi2;
  int h[N], z[N], sz[N], hs[N];
  edge E[N << 1];
  vector<int> A;
  void clear() {
    En = 0;
    memset(h, 0, sizeof h);
  }
  void E_add(int x, int y) {
    E[++En].s = y;
    E[En].n = h[x];
    h[x] = En;
    E[++En].s = x;
    E[En].n = h[y];
    h[y] = En;
  }
  void get_size(int x, int F) {
    sz[x] = 1;
    for (int k = h[x]; k; k = E[k].n)
      if (E[k].s != F) {
        get_size(E[k].s, x);
        sz[x] += sz[E[k].s];
      }
  }
  void get_root(int x, int F) {
    int k, ma = size - sz[x];
    for (k = h[x]; k; k = E[k].n)
      if (E[k].s != F) {
        get_root(E[k].s, x);
        if (sz[E[k].s] > ma) ma = sz[E[k].s];
      }
    if (ma < mi1) {
      mi2 = mi1;
      rt2 = rt1;
      mi1 = ma;
      rt1 = x;
    } else {
      if (ma < mi2) {
        mi2 = ma;
        rt2 = x;
      }
    }
  }
  int get_hash(int x) {
    z[x] = 1;
    vector<int> A;
    for (int k = h[x]; k; k = E[k].n)
      if (!z[E[k].s]) A.push_back(get_hash(E[k].s));
    sort(A.begin(), A.end());
    if (!Map[A]) Map[A] = ++nm;
    return hs[x] = Map[A];
  }
  int Js() {
    memset(z, 0, sizeof z);
    A.clear();
    for (i = 1; i <= n; i++)
      if (!z[i]) {
        get_size(i, 0);
        size = sz[i];
        mi1 = mi2 = oo;
        get_root(i, 0);
        if (mi1 != mi2)
          A.push_back(get_hash(rt1));
        else {
          vector<int> tmp;
          tmp.push_back(-1);
          z[rt2] = 1;
          tmp.push_back(get_hash(rt1));
          z[rt2] = 0;
          tmp.push_back(get_hash(rt2));
          sort(tmp.begin(), tmp.end());
          if (!Map[tmp]) Map[tmp] = ++nm;
          A.push_back(Map[tmp]);
        }
      }
    sort(A.begin(), A.end());
    if (!Map[A]) Map[A] = ++nm;
    return Map[A];
  }
  void work(int x) {
    memset(z, 0, sizeof z);
    z[x] = 1;
    A.clear();
    get_size(x, 0);
    for (int k = h[x]; k; k = E[k].n) {
      size = sz[E[k].s];
      mi1 = mi2 = oo;
      get_root(E[k].s, x);
      if (mi1 != mi2)
        A.push_back(get_hash(rt1));
      else {
        vector<int> tmp;
        tmp.push_back(-1);
        z[rt2] = 1;
        tmp.push_back(get_hash(rt1));
        z[rt2] = 0;
        tmp.push_back(get_hash(rt2));
        sort(tmp.begin(), tmp.end());
        if (!Map[tmp]) Map[tmp] = ++nm;
        A.push_back(Map[tmp]);
      }
    }
    A.push_back(1);
    sort(A.begin(), A.end());
  }
  void dfs(int x, int F, int tmp, int tmp2) {
    int t = ++num, k;
    for (k = h[x]; k; k = E[k].n)
      if (E[k].s != F && E[k].s != tmp && E[k].s != tmp2) {
        Ans[++ans].x = t;
        Ans[ans].y = num + 1;
        dfs(E[k].s, x, tmp, tmp2);
      }
  }
  void dfs2(int x, int F, int tmp, int tmp2, int xx) {
    vector<cc> Tmp;
    int t = ++num, k;
    cc a;
    if (x == xx) Txy = t;
    for (k = h[x]; k; k = E[k].n)
      if (E[k].s != F && E[k].s != tmp && E[k].s != tmp2) {
        a.x = E[k].s;
        a.hs = hs[E[k].s];
        Tmp.push_back(a);
      }
    sort(Tmp.begin(), Tmp.end());
    for (k = 0; k < Tmp.size(); k++) dfs2(Tmp[k].x, x, tmp, tmp2, xx);
  }
  void dfs3(int x, int F, int tmp, int tmp2) {
    vector<cc> Tmp;
    int t = ++num, k;
    cc a;
    for (k = h[x]; k; k = E[k].n)
      if (E[k].s != F && E[k].s != tmp && E[k].s != tmp2) {
        a.x = E[k].s;
        a.hs = hs[E[k].s];
        Tmp.push_back(a);
      }
    sort(Tmp.begin(), Tmp.end());
    for (k = 0; k < Tmp.size(); k++) {
      Ans[++ans].x = t;
      Ans[ans].y = num + 1;
      dfs3(Tmp[k].x, x, tmp, tmp2);
    }
  }
  int find_x(int x, int y) {
    for (int k = h[x]; k; k = E[k].n) {
      size = sz[E[k].s];
      mi1 = mi2 = oo;
      get_root(E[k].s, x);
      if (mi1 != mi2) {
        if (hs[rt1] == y) return E[k].s;
      } else {
        vector<int> tmp;
        tmp.push_back(-1);
        z[rt2] = 1;
        tmp.push_back(hs[rt1]);
        z[rt2] = 0;
        tmp.push_back(hs[rt2]);
        sort(tmp.begin(), tmp.end());
        if (Map[tmp] == y) return E[k].s;
      }
    }
    return 0;
  }
} A, B, C, D;
bool check() {
  int i, j, k, na, nb, nc, fg;
  A.work(x);
  B.work(y);
  j = 0;
  k = 0;
  fg = 0;
  for (i = 0; i < C.A.size(); i++) {
    nc = 1;
    while (i + 1 < C.A.size() && C.A[i + 1] == C.A[i]) i++, nc++;
    na = nb = 0;
    while (j < A.A.size() && A.A[j] == C.A[i]) j++, na++;
    while (k < B.A.size() && B.A[k] == C.A[i]) k++, nb++;
    if (nc != na + nb) {
      if (!na || !nb) return 0;
      if (na + nb - 1 != nc) return 0;
      if (fg) return 0;
      fg = C.A[i];
    }
  }
  ans = 0;
  if (!fg) {
    if (A.sz[x] + B.sz[y] != n) return 0;
    num = 0;
    A.dfs(x, 0, 0, 0);
    px = 1;
    py = num + 1;
    Ans[++ans].x = 1;
    Ans[ans].y = num + 1;
    B.dfs(y, 0, 0, 0);
  } else {
    xx = A.find_x(x, fg);
    yy = B.find_x(y, fg);
    if (A.sz[x] + B.sz[y] - A.sz[xx] != n) return 0;
    num = 0;
    if (A.mi1 != A.mi2) {
      A.dfs2(A.rt1, 0, x, 0, xx);
      tx = Txy;
    } else {
      if (A.hs[A.rt1] < A.hs[A.rt2]) {
        A.dfs2(A.rt1, 0, x, A.rt2, xx);
        A.dfs2(A.rt2, 0, x, A.rt1, xx);
      } else {
        A.dfs2(A.rt2, 0, x, A.rt1, xx);
        A.dfs2(A.rt1, 0, x, A.rt2, xx);
      }
      tx = Txy;
    }
    num = 0;
    if (B.mi1 != B.mi2) {
      B.dfs2(B.rt1, 0, y, 0, yy);
      ty = Txy;
    } else {
      if (B.hs[B.rt1] < B.hs[B.rt2]) {
        B.dfs2(B.rt1, 0, y, B.rt2, yy);
        B.dfs2(B.rt2, 0, y, B.rt1, yy);
      } else {
        B.dfs2(B.rt2, 0, y, B.rt1, yy);
        B.dfs2(B.rt1, 0, y, B.rt2, yy);
      }
      ty = Txy;
    }
    num = 0;
    if (A.mi1 != A.mi2)
      A.dfs3(A.rt1, 0, x, 0);
    else {
      if (A.hs[A.rt1] < A.hs[A.rt2]) {
        A.dfs3(A.rt1, 0, x, A.rt2);
        Ans[++ans].x = 1;
        Ans[ans].y = num + 1;
        A.dfs3(A.rt2, 0, x, A.rt1);
      } else {
        A.dfs3(A.rt2, 0, x, A.rt1);
        Ans[++ans].x = 1;
        Ans[ans].y = num + 1;
        A.dfs3(A.rt1, 0, x, A.rt2);
      }
    }
    px = num + 1;
    Ans[++ans].x = num + 1;
    Ans[ans].y = tx;
    A.dfs(x, 0, xx, 0);
    py = num + 1;
    Ans[++ans].x = num + 1;
    Ans[ans].y = ty;
    B.dfs(y, 0, yy, 0);
  }
  D.clear();
  for (i = 1; i <= ans; i++)
    if (Ans[i].x != py && Ans[i].y != py) D.E_add(Ans[i].x, Ans[i].y);
  if (tA != D.Js()) return 0;
  D.clear();
  for (i = 1; i <= ans; i++)
    if (Ans[i].x != px && Ans[i].y != px) D.E_add(Ans[i].x, Ans[i].y);
  if (tB != D.Js()) return 0;
  puts("YES");
  for (i = 1; i <= ans; i++) printf("%d %d\n", Ans[i].x, Ans[i].y);
  return 1;
}
int main() {
  R(Test);
  for (int ii = 1; ii <= Test; ii++) {
    R(n);
    R(k);
    Fg = na = nb = ta = tb = nm = 0;
    Map.clear();
    A.clear();
    B.clear();
    R(A.m);
    for (i = 1; i <= n; i++) f[i] = i;
    for (i = 1; i <= A.m; i++) {
      R(x);
      R(y);
      A.E_add(x, y);
      if (getf(x) != getf(y))
        f[f[x]] = f[y];
      else
        Fg = 1;
    }
    for (i = 1; i <= n; i++) {
      if (A.h[i])
        na++;
      else if (!ta)
        ta = i;
    }
    if (na >= n) Fg = 1;
    R(B.m);
    for (i = 1; i <= n; i++) f[i] = i;
    for (i = 1; i <= B.m; i++) {
      R(x);
      R(y);
      B.E_add(x, y);
      if (getf(x) != getf(y))
        f[f[x]] = f[y];
      else
        Fg = 1;
    }
    for (i = 1; i <= n; i++) {
      if (B.h[i])
        nb++;
      else if (!tb)
        tb = i;
    }
    if (nb >= n) Fg = 1;
    if (Fg) {
      puts("NO");
      continue;
    }
    tA = A.Js();
    tB = B.Js();
    x = 0;
    y = 0;
    P.clear();
    for (i = 1; i <= n; i++)
      if (A.h[i]) {
        C.clear();
        for (j = 1; j <= n; j++)
          if (j != i)
            for (k = A.h[j]; k; k = A.E[k].n)
              if (A.E[k].s != i && j < A.E[k].s) C.E_add(j, A.E[k].s);
        tt = C.Js();
        if (!P[tt]) P[tt] = i;
      }
    if (na + 2 <= n) {
      C.clear();
      for (j = 1; j <= n; j++)
        if (j != ta)
          for (k = A.h[j]; k; k = A.E[k].n)
            if (A.E[k].s != ta && j < A.E[k].s) C.E_add(j, A.E[k].s);
      tt = C.Js();
      if (!P[tt]) P[tt] = ta;
    }
    for (i = 1; i <= n; i++)
      if (B.h[i]) {
        C.clear();
        for (j = 1; j <= n; j++)
          if (j != i)
            for (k = B.h[j]; k; k = B.E[k].n)
              if (B.E[k].s != i && j < B.E[k].s) C.E_add(j, B.E[k].s);
        tt = C.Js();
        if (P.find(tt) != P.end()) {
          x = P[tt];
          y = i;
          if (check())
            break;
          else
            x = 0;
        }
      }
    if (!x && nb + 2 <= n) {
      C.clear();
      for (j = 1; j <= n; j++)
        if (j != tb)
          for (k = B.h[j]; k; k = B.E[k].n)
            if (B.E[k].s != tb && j < B.E[k].s) C.E_add(j, B.E[k].s);
      tt = C.Js();
      if (P.find(tt) != P.end()) {
        x = P[tt];
        y = tb;
        if (!check()) x = 0;
      }
    }
    if (!x) {
      puts("NO");
      continue;
    }
  }
}