## 1) Abridged problem statement

You are given an undirected graph with **signs on each edge end**: for each edge \(e=\{u,v\}\), two values \(\omega(e,u),\omega(e,v)\in\{-1,+1\}\).

An **elementary transformation** at a vertex \(x\) flips (negates) \(\omega(e,x)\) for every incident edge \(e\).

A bidirected graph corresponds to a usual directed graph iff **for every edge \(\{u,v\}\)**, after some transformations, the two endpoint signs become **opposite**:
\[
\omega(e,u)\cdot \omega(e,v) = -1.
\]

Task:
- Determine if it is possible to reach such a state.
- If possible, output a set of vertices to transform with **minimum size** (any optimal set).

---

## 2) Detailed editorial

### Key observation: transformations are "vertex flips"
Let \(x_v\in\{0,1\}\) indicate whether we flip vertex \(v\) (1 = flipped, 0 = not flipped).

If an endpoint sign is \(d\in\{-1,+1\}\), after flipping vertex \(v\) it becomes:
\[
d' = d \cdot (-1)^{x_v}.
\]

For an edge \(e=\{u,v\}\) with original endpoint signs \(d_u=\omega(e,u)\), \(d_v=\omega(e,v)\), the product after flips is:
\[
d_u' d_v' = (d_u d_v)\cdot (-1)^{x_u+x_v}.
\]

We need \(d_u'd_v'=-1\). Let \(w = d_u d_v \in \{-1,+1\}\). Then:
\[
w\cdot (-1)^{x_u+x_v} = -1
\]
which is equivalent to:
- If \(w = +1\): then \((-1)^{x_u+x_v}=-1\) ⇒ \(x_u+x_v\) is odd ⇒ **\(x_u \ne x_v\)**.
- If \(w = -1\): then \((-1)^{x_u+x_v}=+1\) ⇒ \(x_u+x_v\) is even ⇒ **\(x_u = x_v\)**.

So each edge imposes an XOR constraint:
\[
x_v = x_u \oplus c \quad\text{where } c=
\begin{cases}
1 & \text{if } w=+1\\
0 & \text{if } w=-1
\end{cases}
\]

### Graph coloring view (2-coloring with "same/different" edges)
We can treat \(x_v\) as a 2-color (0/1). For every edge:
- if \(w=+1\), endpoints must have **different** colors,
- if \(w=-1\), endpoints must have **same** colors.

This is exactly a bipartite-like constraint system solvable by BFS/DFS:
- Assign a color to a start vertex.
- Propagate required colors across edges.
- If a contradiction occurs, answer is **NO**.

This is also equivalent to checking consistency of a system of linear equations over GF(2).

### Minimizing number of transformations
Within a **connected component**, once you choose the color of one vertex, all others are forced. There are exactly two solutions in a component: all colors flipped (0↔1).

Flipped vertices are exactly those with \(x_v=1\). To minimize flips in a component, choose the solution with fewer 1s:
- BFS collects vertices of color 0 and color 1,
- add the smaller group to the answer set.

Do this independently per component; sums of minima give the global minimum.

### Complexity
- Build adjacency with constraint \(w=d_1 d_2\).
- BFS each component once.

Time: \(O(n+m)\). Memory: \(O(n+m)\).

---

## 3) C++ Solution

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

---

## 4) Python solution (same approach) with detailed comments

```python
import sys
from collections import deque

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    # Build adjacency list with constraints.
    # For each edge (a,b) with endpoint signs d1,d2, define w = d1*d2 in {-1,+1}.
    # Constraint:
    #   w = +1 => x_a != x_b
    #   w = -1 => x_a == x_b
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        a = int(next(it))
        b = int(next(it))
        d1 = int(next(it))
        d2 = int(next(it))
        w = d1 * d2
        adj[a].append((b, w))
        adj[b].append((a, w))

    # color[v] = assigned value of x_v (0/1), -1 means unassigned/unvisited
    color = [-1] * (n + 1)

    flips = []      # vertices where x_v = 1 in our chosen optimal solution

    for start in range(1, n + 1):
        if color[start] != -1:
            continue

        # Start BFS for this connected component.
        color[start] = 0
        groups = [[], []]         # groups[0] and groups[1] store vertices by color
        groups[0].append(start)

        q = deque([start])
        possible = True

        while q and possible:
            u = q.popleft()
            cu = color[u]

            for v, w in adj[u]:
                # Required color for v given u:
                # if w==+1 => different: need = 1 - cu
                # if w==-1 => same:     need = cu
                need = (1 - cu) if w == 1 else cu

                if color[v] == -1:
                    color[v] = need
                    groups[need].append(v)
                    q.append(v)
                elif color[v] != need:
                    possible = False

        if not possible:
            sys.stdout.write("NO\n")
            return

        # To minimize flips in this component, pick the smaller of the two groups
        # to be x_v = 1 (i.e., vertices we will flip).
        smaller = groups[0] if len(groups[0]) <= len(groups[1]) else groups[1]
        flips.extend(smaller)

    flips.sort()
    out = ["YES", str(len(flips))]
    out.extend(str(v) for v in flips)
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()
```

---

## 5) Compressed editorial

For edge \(\{u,v\}\) with signs \(d_u,d_v\), flipping a vertex negates all its incident signs. Let \(x_v\in\{0,1\}\) be whether \(v\) is flipped. After flips:
\[
(d_u(-1)^{x_u})(d_v(-1)^{x_v}) = (d_ud_v)(-1)^{x_u+x_v}.
\]
We need product \(-1\). Let \(w=d_ud_v\). Then:
- \(w=+1 \Rightarrow x_u\neq x_v\),
- \(w=-1 \Rightarrow x_u=x_v\).

So we 2-color vertices with "different" edges for \(w=+1\) and "same" edges for \(w=-1\). BFS/DFS detects contradictions (⇒ NO). Each connected component has two valid colorings (swap colors). To minimize flips, choose the smaller color class as vertices to flip. Total time \(O(n+m)\).
