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>
template <typename T>
inline T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
inline T min(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline bool repr(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool repl(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline T gcd(T a, T b) {
  T t;
  if (a < b) {
    while (a) {
      t = a;
      a = b % a;
      b = t;
    }
    return b;
  } else {
    while (b) {
      t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
}
template <typename T>
inline T sqr(T x) {
  return x * x;
}
struct Cg {
  __attribute__((always_inline)) inline char operator()() { return getchar(); }
};
struct Cp {
  __attribute__((always_inline)) inline void operator()(char x) { putchar(x); }
};
__attribute__((always_inline)) inline bool IS(char x) {
  return x == 10 || x == 13 || x == ' ';
}
template <typename T>
struct Fr {
  T P;
  __attribute__((always_inline)) inline Fr &operator,(int &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator int() {
    int x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(long long &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator long long() {
    long long x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(char &x) {
    for (x = P(); IS(x); x = P())
      ;
    return *this;
  }
  __attribute__((always_inline)) inline operator char() {
    char x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(char *x) {
    char t = P();
    for (; IS(t); t = P())
      ;
    if (~t) {
      for (; !IS(t) && ~t; t = P()) *x++ = t;
    }
    *x++ = 0;
    return *this;
  }
  __attribute__((always_inline)) inline Fr &operator,(double &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator double() {
    double x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(long double &x) {
    x = 0;
    unsigned char t = P();
    while ((t < '0' || t > '9') && t != '-') t = P();
    bool f = 0;
    if (t == '-') t = P(), f = 1;
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    if (t == '.') {
      double u = 0.1;
      for (t = P(); t >= '0' && t <= '9'; t = P(), u *= 0.1) x += u * (t - '0');
    }
    if (f) x = -x;
    return *this;
  }
  __attribute__((always_inline)) inline operator long double() {
    long double x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(unsigned int &x) {
    x = 0;
    unsigned char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  __attribute__((always_inline)) inline operator unsigned int() {
    unsigned int x;
    *this, x;
    return x;
  }
  __attribute__((always_inline)) inline Fr &operator,(unsigned long long &x) {
    x = 0;
    unsigned char t = P();
    while (t < '0' || t > '9') t = P();
    x = t - '0';
    for (t = P(); t >= '0' && t <= '9'; t = P()) x = x * 10 + t - '0';
    return *this;
  }
  __attribute__((always_inline)) inline operator unsigned long long() {
    unsigned long long x;
    *this, x;
    return x;
  }
};
Fr<Cg> in;
template <typename T>
struct Fw {
  T P;
  __attribute__((always_inline)) inline Fw &operator,(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(int x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(unsigned int x) {
    if (x) {
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(unsigned int x) {
    if (x) {
      unsigned char s[10], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(long long x) {
    if (x) {
      if (x < 0) P('-'), x = -x;
      unsigned char s[19], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(unsigned long long x) {
    if (x) {
      unsigned char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(unsigned long long x) {
    if (x) {
      unsigned char s[20], c = 0;
      while (x) s[c++] = x % 10 + '0', x /= 10;
      while (c--) P(s[c]);
    } else
      P('0');
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(char x) {
    P(x);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(char x) {
    P(x);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator,(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(const char *x) {
    while (*x) P(*x++);
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
  __attribute__((always_inline)) inline Fw &operator()(long double x, int y) {
    if (y) {
      double t = 0.5;
      for (int i = y; i--;) t *= 0.1;
      if (x >= 0)
        x += t;
      else
        x -= t, P('-');
      *this, (long long)(abs(x));
      P('.');
      if (x < 0) x = -x;
      while (y--) {
        x *= 10;
        x -= floor(x * 0.1) * 10;
        P(((int)x) % 10 + '0');
      }
    } else if (x >= 0)
      *this, (long long)(x + 0.5);
    else
      *this, (long long)(x - 0.5);
    ;
    return *this;
  }
};
Fw<Cp> out;
const int N = 1005;
unsigned long long hp[N * 2];
struct tree {
  std::vector<int> p[N];
  int n, m, c, ro, tot, mi, wx, wy, avo, fa[N], sz[N], id[N];
  std::pair<unsigned long long, int> bh[N];
  bool vis[N];
  inline void clear() {
    for (int i = 0, iend = N; i < iend; i++)
      p[i].clear(), fa[i] = sz[i] = id[i] = vis[i] = 0,
                    bh[i] = std::make_pair(0, 0);
    n = m = c = ro = tot = mi = wx = wy = avo = 0;
  }
  inline void read(int _n) {
    n = _n, m = in;
    for (int i = 1, iend = m; i <= iend; i++) {
      int x, y;
      in, x, y;
      p[x].push_back(y);
      p[y].push_back(x);
    }
  }
  inline void dfs1(int x) {
    tot++;
    vis[x] = 1;
    sz[x] = 1;
    for (__typeof((p[x]).end()) i = (p[x]).begin(); i != (p[x]).end(); ++i)
      if (*i != fa[x] && *i != avo) {
        fa[*i] = x;
        dfs1(*i);
        sz[x] += sz[*i];
      }
  }
  inline void dfs2(int x) {
    int t = tot - sz[x];
    for (__typeof((p[x]).end()) i = (p[x]).begin(); i != (p[x]).end(); ++i)
      if (*i != fa[x] && *i != avo) dfs2(*i), repr(t, sz[*i]);
    if (t == mi)
      wy = x;
    else if (t < mi)
      mi = t, wx = x, wy = 0;
  }
  inline unsigned long long getr(
      std::vector<std::pair<unsigned long long, int>> &q, int l, int r) {
    unsigned long long res = l;
    for (__typeof((q).end()) i = (q).begin(); i != (q).end(); ++i)
      res = res * hp[i->second * 2] + i->first;
    return res * hp[1] + r;
  }
  inline unsigned long long dfs3(int x, int fa, bool dbg = 0) {
    std::vector<std::pair<unsigned long long, int>> q;
    sz[x] = 1;
    for (__typeof((p[x]).end()) i = (p[x]).begin(); i != (p[x]).end(); ++i)
      if (*i != fa && *i != avo) {
        q.push_back(std::make_pair(dfs3(*i, x), sz[*i]));
        sz[x] += sz[*i];
      }
    std::sort(q.begin(), q.end());
    return getr(q, 1, 2);
  }
  inline void print(int x, int fa) {
    for (__typeof((p[x]).end()) i = (p[x]).begin(); i != (p[x]).end(); ++i)
      if (*i != fa && *i != avo) {
        print(*i, x);
        out, x, ' ', *i, '\n';
      }
  }
  inline void setvis(int x, int fa) {
    vis[x] = 0;
    for (__typeof((p[x]).end()) i = (p[x]).begin(); i != (p[x]).end(); ++i)
      if (*i != fa) setvis(*i, x);
  }
  inline std::pair<unsigned long long, int> getbhash(int x) {
    fa[x] = 0;
    tot = 0;
    dfs1(x);
    mi = tot;
    dfs2(x);
    if (!wy) return std::make_pair(dfs3(wx, 0), tot);
    assert(mi * 2 == tot);
    unsigned long long a = dfs3(wx, wy), b = dfs3(wy, wx);
    if (a > b) std::swap(a, b);
    a = ((3 * hp[tot] + a) * hp[tot] + b) * hp[1] + 4;
    return std::make_pair(a, tot);
  }
  inline void gethash(
      int fs, std::vector<std::pair<
                  std::pair<unsigned long long,
                            std::pair<unsigned long long, unsigned long long>>,
                  std::pair<int, int>>> &res) {
    c = 0, ro = 1;
    while (p[ro].size()) ro++;
    avo = 0;
    for (int i = 1, iend = n; i <= iend; i++)
      if (!id[i] && i != ro) {
        bh[++c] = getbhash(i);
        for (int j = 1, jend = n; j <= jend; j++)
          if (vis[j]) id[j] = c, vis[j] = 0;
      }
    for (int i = 1, iend = n; i <= iend; i++)
      if (i != ro) {
        avo = i;
        for (int _j = 0; _j <= p[i].size(); _j++) {
          int j = _j < p[i].size() ? p[i][_j] : 0;
          std::vector<std::pair<unsigned long long, int>> qx, qy;
          std::pair<unsigned long long, int> md = std::make_pair(0, 0);
          for (__typeof((p[i]).end()) k = (p[i]).begin(); k != (p[i]).end();
               ++k) {
            if (*k == j)
              md = getbhash(*k);
            else
              qy.push_back(getbhash(*k));
          }
          for (int k = 1, kend = c; k <= kend; k++)
            if (k != id[i]) qx.push_back(bh[k]);
          std::sort(qx.begin(), qx.end());
          std::sort(qy.begin(), qy.end());
          unsigned long long x = getr(qx, 5 + fs * 2, 6 + fs * 2);
          unsigned long long y = getr(qy, 7 - fs * 2, 8 - fs * 2);
          if (fs) std::swap(x, y);
          res.push_back(
              std::make_pair(std::make_pair(md.first, std::make_pair(x, y)),
                             std::make_pair(i, j)));
          setvis(i, 0);
        }
      }
  }
} a, b;
int n;
bool bu[N];
int main() {
  hp[0] = 1;
  for (int i = 1, iend = N * 2 - 1; i <= iend; i++) hp[i] = hp[i - 1] * 103;
  for (int T = in; T--;) {
    in, n;
    (int)in;
    a.read(n);
    b.read(n);
    std::vector<
        std::pair<std::pair<unsigned long long,
                            std::pair<unsigned long long, unsigned long long>>,
                  std::pair<int, int>>>
        ha, hb;
    a.gethash(0, ha);
    b.gethash(1, hb);
    std::map<std::pair<unsigned long long,
                       std::pair<unsigned long long, unsigned long long>>,
             std::pair<int, int>>
        va;
    for (__typeof((ha).end()) i = (ha).begin(); i != (ha).end(); ++i)
      va.insert(*i);
    bool flag = 0;
    std::pair<int, int> ua, ub;
    for (__typeof((hb).end()) i = (hb).begin(); i != (hb).end(); ++i)
      if (va.count(i->first)) {
        flag = 1;
        ua = va[i->first];
        ub = i->second;
        break;
      }
    if (!flag) {
      out, "NO\n";
      a.clear(), b.clear();
      continue;
    }
    out, "YES\n";
    std::multiset<unsigned long long> rv;
    a.avo = ua.first;
    b.avo = ub.first;
    for (__typeof((a.p[ua.first]).end()) i = (a.p[ua.first]).begin();
         i != (a.p[ua.first]).end(); ++i) {
      if (*i != ua.second) {
        rv.insert(a.dfs3(*i, 0));
      }
    }
    std::vector<std::pair<int, int>> fin;
    for (int i = 1, iend = b.c; i <= iend; i++) bu[i] = 0;
    for (int i = 1, iend = n; i <= iend; i++)
      if (i != b.ro && !bu[b.id[i]] && b.id[i] != b.id[ub.first]) {
        unsigned long long th = b.dfs3(i, 0);
        if (rv.count(th)) {
          bu[b.id[i]] = 1;
          fin.push_back(std::make_pair(i, b.ro));
          rv.erase(rv.find(th));
        }
      }
    if (!ua.second) {
      fin.push_back(std::make_pair(ub.first, b.ro));
    } else {
      unsigned long long th = a.dfs3(ua.second, 0);
      b.fa[ub.second] = 0;
      b.dfs1(ub.second);
      for (int i = 1, iend = n; i <= iend; i++)
        if (b.vis[i]) {
          unsigned long long ph = b.dfs3(i, 0);
          if (th == ph) {
            fin.push_back(std::make_pair(i, b.ro));
            break;
          }
        }
    }
    for (int i = 1, iend = n; i <= iend; i++)
      for (__typeof((b.p[i]).end()) j = (b.p[i]).begin(); j != (b.p[i]).end();
           ++j)
        if (*j < i) out, i, ' ', *j, '\n';
    for (__typeof((fin).end()) i = (fin).begin(); i != (fin).end(); ++i)
      out, i->first, ' ', i->second, '\n';
    a.clear(), b.clear();
  }
}