p513.ans1
======================
YES

=================
p513.ans2
======================
NO

=================
p513.ans3
======================
NO

=================
p513.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/graph/dsu.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class DSU {
  public:
    int n;
    vector<int> par;
    vector<int> sz;

    DSU(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
    bool connected(int x, int y) { return root(x) == root(y); }

    int unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) {
            return x;
        }
        if(sz[x] > sz[y]) {
            swap(x, y);
        }
        par[x] = y;
        sz[y] += sz[x];
        return y;
    }

    vector<vector<int>> components() {
        vector<vector<int>> comp(n + 1);
        for(int i = 0; i <= n; i++) {
            comp[root(i)].push_back(i);
        }
        return comp;
    }
};

int n, m;
vector<vector<int>> adj;

void read() {
    cin >> n >> m;
    adj.assign(n, vector<int>(n, 0));
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u][v] = 1;
        adj[v][u] = 1;
    }
}

void solve() {
    // Decide whether the graph is the 3-SAT -> clique reduction graph. In
    // that reduction the 3n vertices split into n clauses of 3 vertices
    // each; vertices inside a clause are pairwise non-adjacent (a triple
    // anti-clique), and two vertices in different clauses are non-adjacent
    // exactly when they are contradictory literals of the same variable.
    //
    // First n must be divisible by 3. Then every vertex must belong to
    // exactly one triangle of mutual non-edges (its clause); we enumerate
    // all such anti-clique triples and require each vertex to appear in
    // precisely one. We add intra-clause edges so the remaining non-edges
    // are only the cross-clause contradictions.
    //
    // Those contradictions must pair literals as x / not-x: build a DSU on
    // 2n nodes (vertex i and its "negation" i+n). A non-edge (i, j) forces
    // i ~ j+n and i+n ~ j. The relation is consistent only if no i is in
    // the same class as i+n.
    //
    // Finally each variable class must contradict every literal of all the
    // other clauses exactly: for class of vertex i with cnt_a positive and
    // cnt_b negative occurrences, the number of cross non-edges it carries
    // (sum of complement-degrees) must equal 2 * cnt_a * cnt_b. If all
    // checks pass, print YES, else NO.

    if(n % 3 != 0) {
        cout << "NO\n";
        return;
    }

    vector<vector<tuple<int, int, int>>> three_anti_cliques_per_node(n);
    vector<int> clique_id(n, -1);
    int cnt_clique_id = 0;

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(adj[i][j] == 0) {
                for(int k = j + 1; k < n; k++) {
                    if(adj[i][k] == 0 && adj[j][k] == 0) {
                        three_anti_cliques_per_node[i].emplace_back(j, k, i);
                        three_anti_cliques_per_node[j].emplace_back(i, k, j);
                        three_anti_cliques_per_node[k].emplace_back(i, j, k);
                        clique_id[i] = clique_id[j] = clique_id[k] =
                            cnt_clique_id++;
                    }
                }
            }
        }
    }

    for(int i = 0; i < n; i++) {
        if(three_anti_cliques_per_node[i].size() != 1) {
            cout << "NO\n";
            return;
        }
    }

    for(int i = 0; i < n; i++) {
        auto [j, k, l] = three_anti_cliques_per_node[i][0];
        adj[i][j] = 1;
        adj[j][i] = 1;
        adj[i][k] = 1;
        adj[k][i] = 1;
        adj[i][l] = 1;
        adj[l][i] = 1;
    }

    DSU dsu(2 * n);
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(adj[i][j] == 0) {
                dsu.unite(i, j + n);
                dsu.unite(i + n, j);
            }
        }
    }

    for(int i = 0; i < n; i++) {
        if(dsu.connected(i, i + n)) {
            cout << "NO\n";
            return;
        }
    }

    vector<int> deg(n, 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(adj[i][j] == 0) {
                deg[i]++;
            }
        }
    }

    for(int i = 0; i < n; i++) {
        int cnt_a = 0, cnt_b = 0, sum = 0;
        for(int v = 0; v < n; v++) {
            if(dsu.connected(i, v)) {
                cnt_a++;
                sum += deg[v];
            }
        }

        for(int v = 0; v < n; v++) {
            if(dsu.connected(i, v + n)) {
                cnt_b++;
                sum += deg[v];
            }
        }

        if(cnt_a * cnt_b * 2 != sum) {
            cout << "NO\n";
            return;
        }
    }

    cout << "YES\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p513.in1
======================
9 22
1 3
1 6
7 1
8 9
9 1
2 3
2 4
2 5
2 6
2 8
3 4
3 5
3 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 9
7 8

=================
p513.in2
======================
6 3
1 6
2 6
3 6

=================
p513.in3
======================
12 51
2 10
7 2
7 1
5 1
5 3
7 9
2 3
1 6
10 3
8 3
6 4
6 7
8 5
11 4
6 12
2 4
11 12
5 9
3 12
1 3
9 12
1 4
10 7
9 10
6 9
3 11
12 10
7 3
9 1
2 1
2 5
12 8
5 6
11 6
12 4
8 1
2 12
6 3
10 5
11 7
2 9
4 5
9 8
10 6
11 2
12 1
10 4
4 8
5 11
4 7
8 10

=================
statement.txt
======================
513. Maximal Clique
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

This is the moment you've been waiting for all your life: you've invented a way to quickly solve the Maximal Clique problem: given an undirected graph find the size of the maximal subset of its vertices that form a clique (are pairwise connected). This problem is NP-hard, meaning you've got a proof that P=NP!

Unfortunately, the scientific community is not so eager to listen to you. Your papers on the subject are being rejected because of "solving an obviously unsolvable problem". Your phone number is already on the ignore list of all Computer Science professors you know. The world seems to hate you.

So you've decided to create a solver for the Maximal Clique problem and put it online, so that everyone can check for himself that you're right. You've already implemented the solver and almost launched the website, but then you've realized that this is not a very good idea: if you make the solver available, everyone will be able to solve every problem from NP by reducing it to the Maximal Clique problem. What if people will just silently use it instead of bringing you fame and respect?

Luckily, the only proof of NP-hardness of the Maximal Clique problem you know works by reducing the 3-SAT problem to it in a very specific way. So you've decided to check if the input graph given to your solver could be obtained from this reduction, and if yes, refuse to solve the problem. That way, nobody will be able to get quick solutions for all problems from NP, but everyone will still be able to verify your solver by feeding other graphs to it.

3-SAT problem statement is: given a formula of form , where each term tji is either some boolean variable or its negation (more formally, either xk or ), check whether there exists some assignment of true/false values to each variable so that the formula evaluates to true. All three terms in one clause must represent different variables.

The reduction works in the following manner. From the above formula, we create a graph with 3n vertices, one for each variable of each clause. Two vertices corresponding to terms tji and tsr are connected when i ≠ r (so the terms belong to different clauses) and those terms are non-contradictory (they are either equal or represent different variables).

The following picture shows the resulting graph for the formula :


Now a clique of size n corresponds to a valid true/false assignment that satisfies at least one term in each clause. The edges highlighted on the above picture form a clique of size 3 and show that setting x1 to false and x2 to true satisfies all clauses, irrespective of the values of x3 and x4.

Given a graph, you need to check if it could be created by the above reduction. The vertices are permuted arbitrarily.

Input
The first line of the input file contains two integers v and e, 1 ≤ v ≤ 100, denoting the number of vertices and edges in the graph. The next e lines contain two integers each, denoting the numbers of vertices connected by an edge. Each pair of vertices are connected at most once, no edge connects a vertex to itself.

Output
Output "YES" when the given graph could be obtained by the given reduction, or "NO" otherwise.

Example(s)
sample input
sample output
9 22
1 3
1 6
7 1
8 9
9 1
2 3
2 4
2 5
2 6
2 8
3 4
3 5
3 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 9
7 8
YES

=================
