<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
## 1) Abridged problem statement (concise)

You are given an undirected graph with \(n\) vertices and \(m\) edges.  
Each edge \(e=\{u,v\}\) has a sign at each endpoint: \(\omega(e,u), \omega(e,v)\in\{-1,+1\}\).

An **elementary transformation** on a vertex \(x\) flips (negates) the signs \(\omega(e,x)\) for all edges incident to \(x\).

Goal:
- Determine whether it’s possible to apply some vertex transformations so that **for every edge \(\{u,v\}\)** the two endpoint signs become **opposite** (i.e. \(\omega'(e,u)\cdot \omega'(e,v)=-1\)), which is exactly the condition for being representable as a directed graph.
- If possible, output a set of vertices to transform with **minimum size** (any optimal solution).

---

## 2) Key observations

### Observation A: flipping vertices is a binary decision
Let
\[
x_v \in \{0,1\}
\]
mean whether we flip vertex \(v\) (1 = flipped).

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

### Observation B: each edge becomes an XOR constraint
For edge \(e=\{u,v\}\) with original endpoint signs \(d_u=\omega(e,u)\), \(d_v=\omega(e,v)\),
\[
d_u' d_v' = (d_u d_v)\cdot (-1)^{x_u + x_v}.
\]
We require \(d_u' d_v' = -1\). Let \(w = d_u d_v \in \{-1,+1\}\). Then:
- If \(w=+1\), we need \((-1)^{x_u+x_v}=-1\) ⇒ \(x_u+x_v\) odd ⇒ **\(x_u \ne x_v\)**.
- If \(w=-1\), we need \((-1)^{x_u+x_v}=+1\) ⇒ \(x_u+x_v\) even ⇒ **\(x_u = x_v\)**.

So every edge says either “same color” or “different color” for the vertex variables \(x_v\).

### Observation C: feasibility = consistent 2-coloring with constraints
This is a graph labeling problem solvable by BFS/DFS:
- propagate required colors,
- detect contradictions ⇒ impossible.

### Observation D: minimum transformations per component
In each connected component:
- choosing \(x\) value for one vertex determines all others,
- the only other solution is flipping all bits (swap 0 ↔ 1),
- to minimize flips, pick the solution with fewer 1s (smaller color class).

---

## 3) Full solution approach

1. **Build constraints.** For each edge \((a,b,d_1,d_2)\), compute:
   \[
   w = d_1 \cdot d_2 \in \{-1,+1\}.
   \]
   Store in adjacency list: \(a \leftrightarrow b\) with label \(w\).
   - \(w=+1\): endpoints must have different \(x\)
   - \(w=-1\): endpoints must have same \(x\)

2. **BFS/DFS each component** to assign colors \(x_v\in\{0,1\}\).
   - Start an unvisited vertex with \(x=0\).
   - For an edge \((u,v,w)\), required color for \(v\) is:
     - if \(w=+1\): \(x_v = 1-x_u\)
     - if \(w=-1\): \(x_v = x_u\)
   - If \(v\) already colored and conflicts with requirement ⇒ output **NO**.

3. **Minimize flips.**
   - During BFS, collect vertices in two groups: color 0 and color 1.
   - Add the smaller group to the answer list (those are vertices we flip).  
     (If equal size, either is fine.)

4. If all components processed without contradiction:
   - output **YES**, number of chosen vertices, and their indices.

**Complexity:**  
Building + BFS over adjacency lists: \(O(n+m)\) time, \(O(n+m)\) memory.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  We solve by reducing to constraints on x_v in {0,1}:
  For each edge e={u,v} with endpoint signs d_u, d_v:
    w = d_u * d_v in {-1, +1}
    If w = +1 => x_u != x_v
    If w = -1 => x_u == x_v

  This is a BFS 2-coloring problem with "same/different" constraints.
  For each connected component, there are exactly two valid colorings (swap 0/1),
  so we choose the smaller color class as flips to minimize transformations.
*/

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

    int n, m;
    cin >> n >> m;

    // adj[u] contains (v, w) where w = d_u * d_v
    vector<vector<pair<int,int>>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b, d1, d2;
        cin >> a >> b >> d1 >> d2;
        int w = d1 * d2; // +1 or -1

        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    // color[v] = x_v in {0,1}, or -1 if not assigned yet
    vector<int> color(n + 1, -1);

    vector<int> flips;      // vertices with x_v = 1 in our chosen optimal solution
    bool possible = true;

    for (int start = 1; start <= n && possible; start++) {
        if (color[start] != -1) continue; // already in some processed component

        // Start BFS for this component
        queue<int> q;
        color[start] = 0;
        q.push(start);

        // groups[0] = vertices with color 0, groups[1] = vertices with color 1
        vector<int> groups[2];
        groups[0].push_back(start);

        while (!q.empty() && possible) {
            int u = q.front();
            q.pop();

            for (auto [v, w] : adj[u]) {
                // Determine required color of v from u and edge label w:
                // w=+1 => different => need = 1 - color[u]
                // w=-1 => same      => need = color[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) {
                    // Contradiction: no assignment can satisfy all edges
                    possible = false;
                    break;
                }
            }
        }

        if (!possible) break;

        // Choose the smaller group as "flipped" (x_v = 1) to minimize flips
        if (groups[0].size() <= groups[1].size()) {
            // Make x_v = 1 for group 0 (equivalent to swapping solution)
            flips.insert(flips.end(), groups[0].begin(), groups[0].end());
        } else {
            flips.insert(flips.end(), groups[1].begin(), groups[1].end());
        }
    }

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

    sort(flips.begin(), flips.end()); // order doesn't matter; sorting is fine
    cout << "YES\n";
    cout << flips.size() << "\n";
    for (int v : flips) cout << v << "\n";

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
from collections import deque

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

    # Build adjacency with constraint label w = d1*d2 in {-1,+1}
    # w=+1 => different colors; w=-1 => same colors
    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 = [-1] * (n + 1)   # -1 = unassigned, else 0/1
    flips = []               # vertices chosen to transform

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

        # BFS this connected component
        q = deque([start])
        color[start] = 0
        groups = [[], []]
        groups[0].append(start)

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

            for v, w in adj[u]:
                # Required color for v:
                # w=+1 => different => 1-cu
                # w=-1 => same      => 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:
                    sys.stdout.write("NO\n")
                    return

        # Minimize flips in this component: choose smaller group to set x_v=1
        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(map(str, flips))
    sys.stdout.write("\n".join(out) + "\n")


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

These implementations follow the same core idea: reduce to “same/different” constraints per edge, BFS to check consistency, and pick the smaller color class per component to minimize the number of vertex flips.