'Twas the night before Christmas, and Santa's frantically setting up his new Christmas tree! There are n nodes in the tree, connected by n-1 edges. On each edge of the tree, there's a set of Christmas lights, which can be represented by an integer in binary representation.

<image>

He has m elves come over and admire his tree. Each elf is assigned two nodes, a and b, and that elf looks at all lights on the simple path between the two nodes. After this, the elf's favorite number becomes the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of the values of the lights on the edges in that path.

However, the North Pole has been recovering from a nasty bout of flu. Because of this, Santa forgot some of the configurations of lights he had put on the tree, and he has already left the North Pole! Fortunately, the elves came to the rescue, and each one told Santa what pair of nodes he was assigned (a_i, b_i), as well as the parity of the number of set bits in his favorite number. In other words, he remembers whether the number of 1's when his favorite number is written in binary is odd or even.

Help Santa determine if it's possible that the memories are consistent, and if it is, remember what his tree looked like, and maybe you'll go down in history!

Input

The first line contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t cases follow.

The first line of each test case contains two integers, n and m (2 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ m ≤ 2 ⋅ 10^5) — the size of tree and the number of elves respectively.

The next n-1 lines of each test case each contains three integers, x, y, and v (1 ≤ x, y ≤ n; -1 ≤ v < 2^{30}) — meaning that there's an edge between nodes x and y. If 

  * v = -1: Santa doesn't remember what the set of lights were on for this edge. 
  * v ≥ 0: The set of lights on the edge is v. 



The next m lines of each test case each contains three integers, a, b, and p (1 ≤ a, b ≤ n; a ≠ b; 0 ≤ p ≤ 1) — the nodes that the elf was assigned to, and the parity of the number of set bits in the elf's favorite number.

It is guaranteed that the sum of all n and the sum of all m don't exceed 2 ⋅ 10^5 each.

It is guaranteed that the given edges form a tree.

Output

For each test case, first print either YES or NO (in any case), whether there's a tree consistent with Santa's memory or not. 

If the answer is YES, print n-1 lines each containing three integers: x, y, and v (1 ≤ x, y ≤ n; 0 ≤ v < 2^{30}) — the edge and the integer on that edge. The set of edges must be the same as in the input, and if the value of some edge was specified earlier, it can not change. You can print the edges in any order.

If there are multiple answers, print any.

Example

Input


4
6 5
1 2 -1
1 3 1
4 2 7
6 3 0
2 5 -1
2 3 1
2 5 0
5 6 1
6 1 1
4 5 1
5 3
1 2 -1
1 3 -1
1 4 1
4 5 -1
2 4 0
3 4 1
2 3 1
3 3
1 2 -1
1 3 -1
1 2 0
1 3 1
2 3 0
2 1
1 2 1
1 2 0


Output


YES
1 2 0
1 3 1
2 4 7
3 6 0
2 5 0
YES
1 2 1
1 3 0
1 4 1
4 5 1
NO
NO

Note

The first test case is the image in the statement.

One possible answer is assigning the value of the edge (1, 2) to 5, and the value of the edge (2, 5) to 3. This is correct because: 

  * The first elf goes from node 2 to node 3. This elf's favorite number is 4, so he remembers the value 1 (as 4 has an odd number of 1 bits in its binary representation). 
  * The second elf goes from node 2 to node 5. This elf's favorite number is 3, so he remembers the value 0 (as 3 has an even number of 1 bits in its binary representation). 
  * The third elf goes from node 5 to node 6. This elf's favorite number is 7, so he remembers the value 1 (as 7 has an odd number of 1 bits in its binary representation). 
  * The fourth elf goes from node 6 to node 1. This elf's favorite number is 1, so he remembers the value 1 (as 1 has an odd number of 1 bits in its binary representation). 
  * The fifth elf goes from node 4 to node 5. This elf's favorite number is 4, so he remembers the number 1 (as 4 has an odd number of 1 bits in its binary representation). 



Note that there are other possible answers.
#include <bits/stdc++.h>
using namespace std;

// loops
#define FOR_3(i, a, b) for (int i = (a), bb##i = (b); i < bb##i; ++i)
#define FORR_3(i, a, b) for (int i = (b)-1, aa##i = (a); i >= aa##i; --i)

#define FOR_2(i, n) FOR_3(i, 0, n)
#define FORR_2(i, n) FORR_3(i, 0, n)

#define FOR_1(n) FOR_2(_i##__LINE__, n)
#define FOR_0() for (;;)

#define OVERLOAD(_0, _1, _2, _3, NAME, ...) NAME
#define FOR(...)                                                               \
  OVERLOAD(_0 __VA_OPT__(, )##__VA_ARGS__, FOR_3, FOR_2, FOR_1, FOR_0)         \
  (__VA_ARGS__)

#define FORR(...)                                                              \
  OVERLOAD(_0 __VA_OPT__(, )##__VA_ARGS__, FORR_3, FORR_2, FORR_1, FOR_0)      \
  (__VA_ARGS__)

// min / max

template <class T> auto min(T &&t) { return move(t); };
template <class T, class... TS> auto min(T &&t, TS &&...ts) {
  auto rest = min(forward<TS>(ts)...);
  return t < rest ? t : rest;
}

template <class T> auto max(T &&t) { return move(t); };
template <class T, class... TS> auto max(T &&t, TS &&...ts) {
  auto rest = max(forward<TS>(ts)...);
  return t > rest ? t : rest;
}

#define REMIN(a, b) ((a) = min(a, b));
#define REMAX(a, b) ((a) = max(a, b));

// containers / arrays
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) int((x).size())
#define ZERO(x) memset(x, 0, sizeof(x));

// other
#define UNUSED(...) (void)(__VA_ARGS__);

// types
#define umap unordered_map
#define vec vector
#define deq deque
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

using vi = vec<int>;
using vll = vec<ll>;
using vpii = vec<pii>;
using vb = vec<bool>;

using di = deq<int>;
using dll = deq<ll>;
using dpii = deq<pii>;

// abbrevs
#define push push_back
#define pop pop_back
#define CMP bool operator<(const auto &o) const

// array operations
#define SORT(v) sort(ALL(v));
#define UNIQUE(c)                                                              \
  {                                                                            \
    SORT(c);                                                                   \
    c.erase(unique(ALL(c)), c.end());                                          \
  }

auto PERM(int n) {
  di v(n);
  FOR(i, n) v[i] = i;
  return v;
}

template <class V> auto esort(const V &v) {
  auto perm = PERM(SZ(v));
  sort(ALL(perm), [&](int a, int b) { return v[a] < v[b]; });
  return perm;
}

template <class V> auto eremap(V &&vv) {
  auto v = move(vv);
  SORT(v);
  umap<typename V::value_type, int> r;
  int nxt = 0;
  for (auto &e : v)
    if (r.emplace(e, nxt).second)
      ++nxt;
  return r;
}

template <class X, class FR, class TO>
bool range(const X &x, const FR &fr, const TO &to) {
  return !(x < fr) && x < to;
}

#ifdef LOCAL
#include <sys/prctl.h>
#include <sys/wait.h>
#include <unistd.h>

void print_trace() {
  char pid_buf[30];
  sprintf(pid_buf, "%d", getpid());
  char name_buf[512];
  name_buf[readlink("/proc/self/exe", name_buf, 511)] = 0;
  prctl(PR_SET_PTRACER, PR_SET_PTRACER_ANY, 0, 0, 0);
  int child_pid = fork();
  if (!child_pid) {
    dup2(2, 1); // redirect output to stderr - edit: unnecessary?
    execl("/usr/bin/gdb", "gdb", "--batch", "-n", "-ex", "thread", "-ex", "bt",
          name_buf, pid_buf, NULL);
    abort(); /* If gdb failed to start */
  } else {
    waitpid(child_pid, NULL, 0);
  }
}

extern const char *const sys_siglist[];

void handler(int sig) {
  cerr << "SIGNAL " << sig << " (" << sys_siglist[sig] << ")" << endl;
  print_trace();
  exit(1);
}

#define INDENT_SIZE 2
string indent;

void _E() { cerr << endl; }
template <class ARG, class... ARGS> void _E(ARG &&arg, ARGS &&...args) {
  cerr << std::forward<ARG>(arg) << " ";
  _E(std::forward<ARGS>(args)...);
}

#define ERR(...)                                                               \
  {                                                                            \
    cerr << indent << "[" << __LINE__ << "] ";                                 \
    _E(__VA_ARGS__);                                                           \
  }

#define _V5(x) #x, "==", (x)
#define _V4(x, ...) #x, "==", (x)__VA_OPT__(, "|", _V5(__VA_ARGS__))
#define _V3(x, ...) #x, "==", (x)__VA_OPT__(, "|", _V4(__VA_ARGS__))
#define _V2(x, ...) #x, "==", (x)__VA_OPT__(, "|", _V3(__VA_ARGS__))
#define _V1(x, ...) #x, "==", (x)__VA_OPT__(, "|", _V2(__VA_ARGS__))
#define ERRV(...) ERR(_V1(__VA_ARGS__))
#define INDENT auto _indenter = Indenter();

struct Indenter {
  Indenter() { FOR(INDENT_SIZE) indent.push_back(' '); }
  ~Indenter() { FOR(INDENT_SIZE) indent.pop_back(); }
};

#define FAIL(str)                                                              \
  {                                                                            \
    cerr << "ASSERT FAILED   " << str << "   " << __FILE__ << ':' << __LINE__  \
         << endl;                                                              \
    abort();                                                                   \
  }

#define SLEEP this_thread::sleep_for(100ms);

#else
#define INDENT
#define SLEEP
#define FAIL(x)                                                                \
  {}
#define ERR(...)                                                               \
  {}
#define ERRV(...)                                                              \
  {}
#endif

// asserts
#define CHECK(cond)                                                            \
  if (!(cond))                                                                 \
  FAIL(#cond)

#define CHECK_OP(op, a, b, res)                                                \
  if (!(res))                                                                  \
  FAIL(#a " " op " " #b "   (" + to_string(a) + " vs " + to_string(b) + ")")

#define CHECK_EQ(a, b) CHECK_OP("==", a, b, (a) == (b))
#define CHECK_NE(a, b) CHECK_OP("!=", a, b, (a) != (b))
#define CHECK_LE(a, b) CHECK_OP("<=", a, b, (a) <= (b))
#define CHECK_GE(a, b) CHECK_OP(">=", a, b, (a) >= (b))
#define CHECK_LT(a, b) CHECK_OP("<", a, b, (a) < (b))
#define CHECK_GT(a, b) CHECK_OP(">", a, b, (a) > (b))

#define CHECK_RANGE(x, a, b)                                                   \
  if (!(a <= x && x < b))                                                      \
  FAIL(#x " in [" #a "," #b ")")

template <class A, class B> auto divup(A a, B b) { return (a + b - 1) / b; }

// bit operations
int msb(int x) {
  CHECK_GT(x, 0)
  return 31 - __builtin_clz(x);
}

int msb(ll x) {
  CHECK_GT(x, 0)
  return 63 - __builtin_clzll(x);
}

int lsb(int x) {
  CHECK_GT(x, 0)
  return __builtin_ctz(x);
}

int lsb(ll x) {
  CHECK_GT(x, 0)
  return __builtin_ctzll(x);
}

int popcount(int x) { return __builtin_popcount(x); }
int popcount(ll x) { return __builtin_popcountll(x); }

#define FORB(b, mask)                                                          \
  for (auto m = mask, bit = lsb(m); m; m ^= (1 << b), bit = lsb(m))

#define FORS(s, mask)                                                          \
  for (auto s = mask; s; s = (s - 1) & mask) // iterate subsets

template <class T> int log2up(T x) { return x <= 1 ? 0 : msb(x - 1) + 1; }

default_random_engine RNG(123);
#define SHUFFLE(c) shuffle(ALL(c), RNG);

// stdin
template <class T> T read() {
  T x;
  cin >> x;
  return x;
}
#define II read<int>()
#define ILL read<ll>()

void _I() {}
template <class ARG, class... ARGS> void _I(ARG &&arg, ARGS &&...args) {
  cin >> arg;
  _I(forward<ARGS>(args)...);
}
#define I(...) _I(__VA_ARGS__);

// stdout
template <class T> void _print(T x) {
  cout << x;
  bool space = true;
  if constexpr (is_same_v<T, char>) {
    if (x == '\n')
      space = false;
  }
  if (space)
    cout << " ";
}
template <class T> void _print(deq<T> &d) {
  for (auto &e : d)
    cout << e << " ";
}
void _O() {}
template <class ARG, class... ARGS> void _O(ARG &&arg, ARGS &&...args) {
  _print(arg);
  _O(forward<ARGS>(args)...);
}
#define O(...) _O(__VA_ARGS__ __VA_OPT__(, ) '\n');
#define OO(...) _O(__VA_ARGS__);

// stderr
template <class T> auto &operator<<(ostream &os, deq<T> &v) {
  os << "{";
  bool first = true;
  for (auto &e : v) {
    if (first)
      first = false;
    else
      os << " ";
    os << e;
  }
  return os << "}";
}

template <class A, class B> auto &operator<<(ostream &os, pair<A, B> &p) {
  return os << "{" << p.first << " " << p.second << "}";
}

////////////////////////////////////////////////////////////////////////////////
//
// snippets/graph.hpp
//

template <class _V, class _E> struct Graph {
  struct V : _V {

    V(_V &&v = _V()) : _V(move(v)) {}
    vi ve;
  };
  vec<V> vs;
  auto &operator[](int i) {
    CHECK_GT(i, 0);
    while (i >= SZ(vs))
      vs.emplace_back();
    return vs[i];
  }
  int size() { return SZ(vs); }

  struct E : _E {
    E(_E &&e = _E()) : _E(move(e)) {}

    struct EV {
      int dest = -1;
      int ith = -1;
    };

    array<EV, 2> ev;
    auto &operator[](int i) { return ev[i]; }
  };
  vec<E> es;

  int dest(int v, int ve) {
    int e = vs[v].ve[ve];
    int ith = es[e][1].dest != v;
    return es[e][ith].dest;
  }

  void e(int a, int b, _E &&_e = _E()) {
    CHECK_NE(a, b);
    operator[](a);
    operator[](b);
    vs[a].ve.push(SZ(es));
    vs[b].ve.push(SZ(es));
    es.emplace_back(move(_e));
    es.back()[0] = {a, SZ(vs[a].ve) - 1};
    es.back()[1] = {b, SZ(vs[b].ve) - 1};
  }
};

struct V {
  int w = -1;
};
struct E {
  int w = -1;
  int orig = -1;
};

using G = Graph<V, E>;
////////////////////////////////////////////////////////////////////////////////

template <class GG> struct DFS {
  struct S {
    int v;
    int ve;
  };

  virtual void visit(GG &, int) {}
  virtual bool visit(GG &, int, int, int) { return true; }

  vb vis;

  void run(GG &g) { FOR(i, 1, SZ(g)) run(g, i); }

  void run(GG &g, int v0) {
    vis.resize(SZ(g));
    if (vis[v0])
      return;

    vec<S> s;

    s.push({v0, 0});
    vis[v0] = 1;
    visit(g, v0);

    while (!s.empty()) {
      auto [v, ve] = s.back();
      if (ve >= SZ(g[v].ve)) {
        s.pop();
        continue;
      }
      s.back().ve++;

      int e = g[v].ve[ve];
      int dest = g.dest(v, ve);

      int p = 0;
      if (SZ(s) - 2 >= 0)
        p = s[SZ(s) - 2].v;

      if (dest != p && visit(g, v, dest, e) && !vis[dest]) {
        s.push({dest, 0});
        vis[dest] = 1;
        visit(g, dest);
      }
    }
  }
};

////////////////////////////////////////////////////////////////////////////////
//  _          _     _   _                                                    //
// | |        | |   | | | |                                                   //
// | |     ___| |_  | |_| |__   ___    __ _  __ _ _ __ ___   ___              //
// | |    / _ \ __| | __| '_ \ / _ \  / _` |/ _` | '_ ` _ \ / _ \             //
// | |___|  __/ |_  | |_| | | |  __/ | (_| | (_| | | | | | |  __/             //
// \_____/\___|\__|  \__|_| |_|\___|  \__, |\__,_|_| |_| |_|\___|             //
//                                     __/ |                                  //
//                                    |___/                                   //
//  ██████▓▓▒▒░░░░░░▒▒▒▒▒▒▒▒░░░░▒▒▒▒░░▒▒▒▒░░░░░░░░▒▒▒▒▒▒▒▒░░░░░░░░░░░░██████  //
//  ██████░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒░░░░░░░░░░▒▒░░▒▒░░░░░░░░░░░░  ░░▒▒████  //
//  ████░░░░░░░░░░▒▒░░░░░░░░░░░░░░░░▒▒▒▒▒▒░░░░▒▒░░░░▒▒    ░░░░░░░░░░  ░░████  //
//  ████░░░░░░▒▒▓▓████▓▓▓▓▓▓░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒░░░░▒▒▓▓▓▓████▓▓▒▒░░  ▓▓██  //
//  ████░░▒▒▓▓██████▓▓▓▓▓▓▓▓██▒▒░░░░░░░░▓▓▓▓░░░░░░░░██▓▓▓▓▒▒▒▒████▓▓▒▒░░████  //
//  ████▓▓▒▒▒▒▓▓████▓▓▓▓██▓▓████░░░░░░░░▒▒▒▒░░░░░░████▓▓▓▓▓▓░░▓▓██▓▓░░░░████  //
//  ████▒▒▒▒▓▓▓▓████▓▓▓▓▓▓▓▓████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▓▓▓▓▓▓▒▒████▓▓░░░░▓▓██  //
//  ████▒▒▒▒▒▒▓▓▓▓██████▓▓██████░░▒▒▒▒▒▒▒▒▒▒░░░░░░████▓▓▓▓▓▓████▓▓▒▒░░░░▓▓██  //
//  ████▓▓▓▓▓▓▒▒▓▓▓▓▓▓██████▓▓▒▒▒▒▒▒▒▒░░▒▒░░░░░░░░▒▒████████▓▓▓▓▒▒░░▒▒▒▒░░██  //
//  ██▓▓░░░░▒▒▓▓██▒▒▒▒▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░▒▒▓▓▓▓▒▒▒▒▒▒▓▓▓▓░░▒▒██  //
//  ██░░▓▓▓▓▒▒▒▒▒▒▓▓▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░    ░░░░░░░░▒▒░░▒▒▓▓▒▒░░░░░░▓▓  //
//  ██░░░░▒▒▓▓▓▓▒▒▓▓▓▓▒▒▒▒▒▒░░▒▒░░░░░░░░░░░░      ░░░░░░░░▒▒▒▒▓▓▒▒▒▒▓▓▓▓▒▒▒▒  //
//  ▓▓▒▒▒▒▒▒░░▓▓▓▓▒▒▓▓▒▒▒▒▒▒░░░░░░░░░░░░░░░░      ░░░░░░░░▒▒▓▓▓▓▒▒▓▓░░        //
//  ▓▓▒▒▒▒▓▓▒▒▒▒▓▓▒▒▓▓▓▓▒▒▒▒░░░░░░░░░░░░░░░░      ░░░░░░▒▒▒▒██▒▒▓▓▓▓░░▒▒▒▒▒▒  //
//  ▓▓▒▒░░░░▓▓░░▓▓▓▓▒▒▓▓▒▒▒▒░░░░░░░░░░░░░░░░        ░░▒▒▒▒▓▓▓▓▒▒▓▓▒▒▒▒░░  ░░  //
//  ██▒▒▒▒░░▒▒▓▓▒▒▓▓▒▒▓▓▒▒▒▒░░░░░░░░░░░░░░░░        ░░░░▒▒▓▓▓▓▒▒▓▓░░▓▓  ▒▒    //
//  ██▒▒▒▒▒▒▒▒▓▓░░▓▓▒▒▓▓▒▒▒▒▒▒░░░░░░░░░░░░░░      ░░░░▒▒▒▒▒▒▓▓░░▓▓░░▓▓░░░░▓▓  //
//  ██▓▓▓▓▓▓▓▓▒▒▒▒▓▓▒▒▓▓▒▒▒▒▒▒▒▒░░░░░░░░░░░░    ░░▒▒▒▒▒▒▒▒▒▒▓▓▒▒▓▓░░▒▒▒▒░░██  //
//  ████▓▓▒▒▒▒▓▓▓▓▒▒▓▓▒▒▒▒▓▓▒▒▒▒░░░░░░░░░░░░      ░░▓▓▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▓▒▒████  //
//  ██████████▓▓▒▒▒▒▒▒▒▒██▓▓▓▓▒▒░░░░░░░░░░░░      ░░░░░░▒▒▒▒░░▒▒▒▒▓▓████████  //
//  ██████████████░░░░░░▒▒██▓▓▓▓██▓▓░░░░░░░░    ▓▓▒▒▒▒▓▓▓▓▒▒░░  ▒▒██████████  //
//  ████████████████░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░▒▒▓▓▓▓▓▓▓▓▒▒▒▒      ████████████  //
//  ████████████████░░░░░░▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒░░      ░░████████████  //
//  ████████████████░░░░░░▒▒░░▒▒▒▒░░▒▒▒▒▒▒▒▒▒▒░░░░░░▒▒        ██████████████  //
//  ████████████████▒▒░░░░▒▒░░░░░░░░░░░░▒▒▒▒░░░░░░░░▒▒░░    ▒▒██████████████  //
//  ██████████████████░░░░▒▒░░░░░░░░░░▒▒▒▒▒▒▒▒░░░░  ▓▓░░    ████████████████  //
//  ██████████████████░░░░▒▒░░░░░░░░░░▒▒▒▒▒▒▒▒░░░░  ▓▓░░  ▓▓████████████████  //
//                                                                            //
//           ;;;;;              ██████╗ ███████╗ ██████╗ ██╗███╗   ██╗        //
//           ;;;;;              ██╔══██╗██╔════╝██╔════╝ ██║████╗  ██║        //
//           ;;;;;              ██████╔╝█████╗  ██║  ███╗██║██╔██╗ ██║        //
//         ..;;;;;..            ██╔══██╗██╔══╝  ██║   ██║██║██║╚██╗██║        //
//          ':::::'             ██████╔╝███████╗╚██████╔╝██║██║ ╚████║        //
//            ':`               ╚═════╝ ╚══════╝ ╚═════╝ ╚═╝╚═╝  ╚═══╝        //
//                                                                            //

const bool MULTIPLE_TEST_CASES = 1;

struct Dfs : DFS<G> {
  bool good = true;

  void visit(G &g, int v) {
    if (g[v].w == -1)
      g[v].w = 0;
  }

  bool visit(G &g, int p, int v, int e) {
    ERRV(p, v, e)
    int want = g[p].w ^ g.es[e].w;
    if (g[v].w > -1 && g[v].w != want)
      good = false;
    g[v].w = want;
    return true;
  }
};

struct Dfs_print : DFS<G> {
  bool visit(G &g, int p, int v, int e) {
    OO(p, v)
    int w = g.es[e].orig;
    if (w == -1)
      w = g[v].w ^ g[p].w;
    O(w)
    return true;
  }
};

struct Test_Case {
  struct Pt {
    array<int, 2> x;
    int c;
    bool operator<(const Pt &o) const { return x < o.x; }
  };
  deq<Pt> pts;

  ll n, m, k, q;
  dll in;

  G g, g2;

  Test_Case() {
    I(n, m)
    // FOR(n) pts.push({{II, II}, II});

    auto add = [&](int a, int b, int w) {
      w = popcount(w) % 2;
      g2.e(a, b, {w});
    };

    FOR(n - 1) {
      int a = II;
      int b = II;
      int w = II;
      g.e(a, b, {w, w});
      if (w > -1) {
        add(a, b, w);
      }
    }

    FOR(m) {
      int a = II;
      int b = II;
      int w = II;
      add(a, b, w);
    }
    //

    Dfs dfs;
    dfs.run(g2);

    if (dfs.good) {
      O("YES")
      Dfs_print().run(g);
    } else
      O("NO")
  }

  int yes = -1;
};

//                                                                            //
// ════════════ ('\../') ═════════════                                        //
// ════════════ (◕.◕) ═══════════════                                        //
// ════════════ (,,)(,,) ═════════════                                        //
// .▀█▀.█▄█.█▀█.█▄.█.█▄▀　█▄█.█▀█.█─█.                                        //
// ─.█.─█▀█.█▀█.█.▀█.█▀▄　─█.─█▄█.█▄█- for reading my code!                   //
// ═══════════════════════════════════              --Adam                    //
////////////////////////////////////////////////////////////////////////////////

int main() {
#ifdef LOCAL
  signal(SIGSEGV, handler);
  signal(SIGABRT, handler);
#endif
  ios_base::sync_with_stdio(0);
  cout.precision(20);
  cout << fixed;

  int num_cases = 1;
  if (MULTIPLE_TEST_CASES)
    cin >> num_cases;

  FOR(i, num_cases) {
    ERR()
    ERR("TEST CASE", i + 1)
    INDENT
    Test_Case tc;
    if (tc.yes != -1)
      O(tc.yes ? "YES" : "NO")
  }

  return 0;
}
