p381.in1
======================
4 3
1 3 -1 -1
2 3 -1 -1
3 4 1 1

=================
p381.cpp
======================
#include <bits/stdc++.h>

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;
};

int n, m;
vector<tuple<int, int, int, int>> edges;

void read() {
    cin >> n >> m;
    edges.resize(m);
    for(auto& [a, b, d1, d2]: edges) {
        cin >> a >> b >> d1 >> d2;
    }
}

void solve() {
    // The problem asks to convert a bidirected graph to a directed graph using
    // minimal elementary transformations (negating all signs at a vertex).
    // For each edge, d_u * d_v must become -1. Flipping vertex v negates its
    // signs. This gives a system of parity constraints per edge:
    //   d_u * d_v = 1  => x_u != x_v (exactly one must flip)
    //   d_u * d_v = -1 => x_u == x_v (both or neither flip)
    // This is a 2-coloring / bipartiteness check. Per connected component,
    // we pick the color class with fewer vertices to minimize flips.

    vector<vector<pair<int, int>>> adj(n + 1);
    for(auto& [a, b, d1, d2]: edges) {
        int w = d1 * d2;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    vector<int> color(n + 1, -1);
    vector<int> flips;
    bool possible = true;

    for(int start = 1; start <= n && possible; start++) {
        if(color[start] != -1) {
            continue;
        }
        color[start] = 0;

        vector<vector<int>> groups(2);
        queue<int> q;
        q.push(start);
        groups[0].push_back(start);

        while(!q.empty() && possible) {
            int u = q.front();
            q.pop();
            for(auto [v, w]: adj[u]) {
                int need = (w == 1) ? (1 - color[u]) : color[u];
                if(color[v] == -1) {
                    color[v] = need;
                    groups[need].push_back(v);
                    q.push(v);
                } else if(color[v] != need) {
                    possible = false;
                }
            }
        }

        if(possible) {
            auto& smaller =
                (groups[0].size() <= groups[1].size()) ? groups[0] : groups[1];
            for(int v: smaller) {
                flips.push_back(v);
            }
        }
    }

    if(!possible) {
        cout << "NO\n";
        return;
    }

    sort(flips.begin(), flips.end());
    cout << "YES\n";
    cout << flips.size() << "\n";
    for(int v: flips) {
        cout << v << "\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();
        solve();
    }

    return 0;
}

=================
p381.ans2
======================
NO

=================
p381.in2
======================
3 3
1 2 1 1
2 3 1 1
1 3 1 1

=================
p381.ans1
======================
YES
1
3

=================
statement.txt
======================
381. Bidirected Graph
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



The notion of bidirected graphs is used to formulate and solve wide range of combinatorial optimization problems: matchings, b-matchings, T-joins, T-paths packing and so on. Bidirected graph is a generalization of directed graph, where every arc has two orientations — one for every end.

More formally, bidirected graph is a tuple (V, E, ends, ω). V is a set of nodes, E is a set of edges, ends is a mapping from E: ends(e) = {u, v}, where u, v ∈ V, u ≠ v. For every e ∈ E and v ∈ ends(e) we define ω(e, v) ∈ {-1, +1}. It is called the direction of the edge e in the node v.

An s-t walk in a bidirected graph G is an alternating sequence

P = (s = v0, e1, v1,..., ek, vk = t),

where vi ∈ V, ei ∈ E, ends(ei) = {vi - 1, vi} and ω(ei + 1, vi) ω(ei, vi) = -1.

A directed graph without loops can be considered as bidirected, if we replace each arc a = (u, v) with an edge ea, and put ends(ea) = {u, v}, ω(ea, u) = -1, ω(ea, v) = +1.

An elementary transformation on node v is defined as follows: if for e ∈ E, ω(e, v) is defined, then negate it. It's clear that elementary transformations don't change the set of walks in G.

We want to determine if it is possible to convert bidirected graph to "directed" graph (i.e. to graph that can be obtained from some directed graph by means of the consideration described above) using several elementary transformations. If it is, we also want to know how to do it using the minimal number of elementary transformations.

Input
The first line of the input contains two integer numbers n and m — the number of vertices and the number of edges in the graph (, ). Next m lines describe the edges of the graph. Each line consists of four numbers ai, bi, di,1, di,2, where ai and bi are the ends of the egde e and di,1=ω(e,ai), di,2=ω(e,bi); 1 ≤ ai, bi ≤ n, di,j ∈ {-1, 1}.

Output
If it is impossible to perform required transformation, output should contain exactly one string "NO" (quotes for clarity only). Otherwise, the first line should contain string "YES", the second line should contain the number of elementary transformations in your solution, and the following lines should describe those transformations. Each transformation should be described by exactly one number — the index of the vertex of this transformation. If there are several answers with the minimal number of transformations, output any of them.

Example(s)
sample input
sample output
4 3
1 3 -1 -1
2 3 -1 -1
3 4 1 1
YES
1
3

sample input
sample output
3 3
1 2 1 1
2 3 1 1
1 3 1 1
NO

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