[HDU 3062] Party (2-sat)

/* http://acm.hdu.edu.cn/showproblem.php?pid=3062 */

// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

// #include <bits/stdc++.h>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

// #define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// using pii = pair<int, int>;
// template<typename T>
// using prior = priority_queue<T, vector<T>, greater<T>>;
// template<typename T>
// using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(0, 1); \
                 auto rnd = bind(__dis, __gen);

const int INF = 1E18;
const int mod = 1E9 + 7;
const int maxn = 2000 + 5;

int scc[maxn], vis[maxn];
vector<int> order;
vector<int> adj[maxn], rev[maxn];

void dfs_rev(int now) {
    vis[now] = 1;
    for (auto x : rev[now]) {
        if (!vis[x]) dfs_rev(x);
    }
    order.eb(now);
}

void dfs(int now, int scc_cnt) {
    scc[now] = scc_cnt;
    for (auto x : adj[now]) {
        if (scc[x] == -1) dfs(x, scc_cnt);
    }
}

void kosaraju(int n) {
    memset(vis, 0x00, sizeof(vis));
    memset(scc, 0xff, sizeof(scc));
    order.clear();

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) dfs_rev(i);
    }

    int scc_cnt = 1;
    for (int i = n-1; i >= 0; --i) {
        int now = order[i];
        if (scc[now] == -1) dfs(now, scc_cnt++);
    }
}

void solve(int n, int m) {
    for (int i = 0; i < 2*n; ++i) adj[i].clear(), rev[i].clear();

    for (int i = 0; i < m; ++i) {
        int a1, a2, c1, c2, id1, id2;
        scanf("%d%d%d%d", &a1, &a2, &c1, &c2);
        id1 = 2*a1 + c1, id2 = 2*a2 + c2;
        adj[id1].eb(id2^1), rev[id2^1].eb(id1);
        adj[id2].eb(id1^1), rev[id1^1].eb(id2);
    }

    kosaraju(2 * n);

    for (int i = 0; i < 2*n; i += 2) {
        // cerr << scc[i] << " " << scc[i^1] << "\n";
        if (scc[i] == scc[i^1]) {puts("NO"); return;}
    }

    puts("YES");
}

int32_t main() {
    // fastIO();

    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) solve(n, m);

    return 0;
}