1001 - Winner Prediction

有 $n$ 个人打比赛，其中 $m_1$ 场已经比完且知道输赢，还剩 $m_2$ 场没有比，问你 $1$ 号选手能不能成为冠军。成为冠军的条件是胜场最多，如果胜场并列每个人都是冠军。

显然第一件事情是所有有关 $1$ 的比赛让 $1$ 号赢。对于一个选手 $i$，记胜场为 $win_i$，如果有 $win_i > win_1$ 那么输出 $NO$。否则他接下来还能赢 $win_1 - win_i$ 场。

考虑建网络流：

• 每一场未进行的比赛用一个新的点表示，源点向其连边
• 第 $i$ 场比赛向他的两个参赛选手连容量为 $1$ 的边
• 对于第 $i$ 个参赛选手向汇点连容量为 $win_1 - win_i$ 的边

跑最大流，若最大流等于 $m_2场比赛-有关1的比赛场数$ 即为 $YES$，否则为 $NO$。

观察到这个网络的结构：源点-> 比赛节点 -> 选手节点 -> 汇点。实际上是一个二分图，dinic的复杂度是 $O(m\sqrt n)$。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class flow_graph {
 public:
  static constexpr T eps = (T) 1e-9;

  struct edge {
    int from;
    int to;
    T c;
    T f;
  };

  vector<vector<int>> g;
  vector<edge> edges;
  int n;
  int st;
  int fin;
  T flow;

  flow_graph(int _n, int _st, int _fin) : n(_n), st(_st), fin(_fin) {
    assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);
    g.resize(n);
    flow = 0;
  }

  void clear_flow() {
    for (const edge &e : edges) {
      e.f = 0;
    }
    flow = 0;
  }

  int add(int from, int to, T forward_cap, T backward_cap) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    g[from].push_back(id);
    edges.push_back({from, to, forward_cap, 0});
    g[to].push_back(id + 1);
    edges.push_back({to, from, backward_cap, 0});
    return id;
  }
};

template <typename T>
class dinic {
public:
  flow_graph<T> &g;

  vector<int> ptr;
  vector<int> d;
  vector<int> q;

  dinic(flow_graph<T> &_g) : g(_g) {
    ptr.resize(g.n);
    d.resize(g.n);
    q.resize(g.n);
  }

  bool expath() {
    fill(d.begin(), d.end(), -1);
    q[0] = g.fin;
    d[g.fin] = 0;
    int beg = 0, end = 1;
    while (beg < end) {
      int i = q[beg++];
      for (int id : g.g[i]) {
        const auto &e = g.edges[id];
        const auto &back = g.edges[id ^ 1];
        if (back.c - back.f > g.eps && d[e.to] == -1) {
          d[e.to] = d[i] + 1;
          if (e.to == g.st) {
            return true;
          }
          q[end++] = e.to;
        }
      }
    }
    return false;
  }

  T dfs(int v, T w) {
    if (v == g.fin) {
      return w;
    }
    int &j = ptr[v];
    while (j >= 0) {
      int id = g.g[v][j];
      const auto &e = g.edges[id];
      if (e.c - e.f > g.eps && d[e.to] == d[v] - 1) {
        T t = dfs(e.to, min(e.c - e.f, w));
        if (t > g.eps) {
          g.edges[id].f += t;
          g.edges[id ^ 1].f -= t;
          return t;
        }
      }
      j--;
    }
    return 0;
  }

  T max_flow() {
    while (expath()) {
      for (int i = 0; i < g.n; i++) {
        ptr[i] = (int) g.g[i].size() - 1;
      }
      T big_add = 0;
      while (true) {
        T add = dfs(g.st, numeric_limits<T>::max());
        if (add <= g.eps) {
          break;
        }
        big_add += add;
      }
      if (big_add <= g.eps) {
        break;
      }
      g.flow += big_add;
    }
    return g.flow;
  }

  vector<bool> min_cut() {
    max_flow();
    vector<bool> ret(g.n);
    for (int i = 0; i < g.n; i++) {
      ret[i] = (d[i] != -1);
    }
    return ret;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<int> win(n);
    for (int i = 0; i < m1; i++) {
      int u, v, z;
      cin >> u >> v >> z;
      u--; v--;
      win[z ? u : v]++;
    }
    int st = n + m2, fin = st + 1;
    flow_graph<int> g(n + m2 + 2, st, fin);
    int flow = 0;
    for (int i = 0; i < m2; i++) {
      int u, v;
      cin >> u >> v;
      u--; v--;
      if (!u || !v) {
        win[0]++;
        flow++;
      } else {
        g.add(i + n, u, 1, 0);
        g.add(i + n, v, 1, 0);
        g.add(st, i + n, 1, 0);
      }
    }
    bool ok = true;
    for (int i = 1; i < n; i++) {
      if (win[i] > win[0]) {
        ok = false;
        break;
      }
    }
    if (!ok) {
      cout << "NO\n";
      continue;
    }
    for (int i = 1; i < n; i++) {
      g.add(i, fin, win[0] - win[i], 0);
    }
    dinic<int> d(g);
    cout << (d.max_flow() == m2 - flow ? "YES" : "NO") << '\n';
  }
  return 0;
}