<|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.

270. Thimbles
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



There is a new game "thimbles" in the Berland's casino. The rules of the game are pretty simple. Croupier places N thimbles on the table and puts a ball under the first of them. Afterwards he shuffles the thimbles and asks a player "Where is the ball?". If the player guesses right, he wins, otherwise he loses. Artful professor Zhuglov noticed, that during the whole day the croupier shuffles thimbles with exactly M swap operations. The set of operations remains invariable, but their order may vary. Swap operation, term introduced by professor Zhuglov, is defined as interchange of two thimbles in positions Ai and Bi. Professor Zhuglov is your scientific advisor, and you are to write a program for him that will determine all possible thimbles that can have the ball inside after the shuffling.

Input
The first line of the input file contains integer numbers N and M (2 <= N <= 100, 1 <= M <= 1000). Each of the following M lines contains two integer numbers Ai and Bi -- swap operation description (1 <= Ai < Bi <= N).

Output
Output the answer for the problem. Numbers can be printed in any order. Adjacent numbers should be delimited by a space.

Sample test(s)

Input
4 3
1 2
1 2
2 3

Output
1 3

Note
There are 3 ways of applying the operations. They are (1,2)-(1,2)-(2,3), (1,2)-(2,3)-(1,2) and (2,3)-(1,2)-(1,2). In the first case a ball will be moved form 1 to 2, and with the 2-nd operation will be returned to 1. In the second case a ball will be moved from 1 to 2 then from 2 to 3. In the third case a ball will be moved by the second operation from 1 to 2 and will be returned to 1 by the third operation.
Author:	Andrew V. Lazarev
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

<|response|>
## 1. Abridged problem statement

There are `N` thimbles numbered `1..N`. Initially the ball is under thimble `1`.

We are given `M` swap operations `(Ai, Bi)`. The croupier will perform all these swaps exactly once, but in any order.

Find all possible final positions of the ball.

---

## 2. Key observations

### Observation 1: Swaps form a multigraph

Create an undirected multigraph:

- vertices = thimbles `1..N`
- each swap `(a, b)` = one undirected edge between `a` and `b`
- multiple identical swaps become parallel edges

When an edge is processed:

- if the ball is at one endpoint, it moves across the edge
- otherwise, the ball stays where it is

Therefore, the edges that actually move the ball form a **trail**: an edge-disjoint walk starting from vertex `1`.

---

### Observation 2: Unused edges can be inserted if the trail visits a safe vertex

Suppose the ball follows some trail `T`, and let `S(T)` be the set of vertices visited by this trail.

An edge `{x, y}` not used by the trail can be performed without moving the ball if, at some moment, the ball is at a vertex different from both `x` and `y`.

So we need:

```text
S(T) \ {x, y} is non-empty
```

If the trail visits at least `3` distinct vertices, then every unused edge is safe, because an edge has only two endpoints.

Thus, most targets are easy once we can find a trail from `1` to that target visiting at least `3` vertices.

---

### Observation 3: Hard cases happen only when the trail visits 1 or 2 vertices

If target `u` is reachable from `1` by a path of length at least `2`, then that path already visits at least `3` vertices:

```text
1 -> ... -> u
```

So such `u` is always possible.

The special cases are:

1. `u = 1`
2. `u` is directly adjacent to `1`

---

## 3. Full solution approach

Let `dist[u]` be the shortest distance from vertex `1` to vertex `u` in the multigraph, ignoring multiplicities.

We test every possible final position `u`.

---

### Case A: `u` is unreachable from `1`

If `dist[u] == -1`, then no trail can reach `u`.

So `u` is impossible.

---

### Case B: `u != 1` and `dist[u] >= 2`

There is a path from `1` to `u` with length at least `2`, so it visits at least `3` vertices.

Therefore, all unused edges can be inserted safely.

So `u` is possible.

---

### Case C: `u != 1` and `u` is adjacent to `1`

Let:

```text
x = number of edges between 1 and u
```

Temporarily remove all direct edges `{1, u}`.

#### C1. Alternative path exists

If `1` can still reach `u`, then there is a path of length at least `2`.

That trail visits at least `3` vertices, so `u` is possible.

#### C2. No alternative path, and `x` is odd

Then we can use all direct `{1, u}` edges:

```text
1 -> u -> 1 -> u -> ...
```

Since `x` is odd, we finish at `u`.

No direct `{1, u}` edge remains unused, so all other unused edges can be inserted safely while the ball is at either `1` or `u`.

So `u` is possible.

#### C3. No alternative path, and `x` is even`

Using all direct edges would end at `1`, not `u`.

To finish at `u`, we need to use an odd number of direct `{1, u}` edges and leave at least one unused. But then the trail must visit a third vertex, so that the unused direct edge can be inserted safely.

This is possible if, after removing `{1, u}` edges, either `1` or `u` lies on a cycle.

A vertex lies on a cycle iff it has at least one incident edge that is not a bridge.

---

### Case D: `u = 1`

We need a closed trail starting and ending at `1`.

There are three possibilities.

#### D1. No edge touches vertex `1`

Then the ball never moves.

So `1` is possible.

#### D2. Two-vertex oscillation

If there exists some vertex `w` such that the multiplicity of edge `{1, w}` is even and at least `2`, then we can use all those edges:

```text
1 -> w -> 1 -> w -> ... -> 1
```

This ends at `1`.

So `1` is possible.

#### D3. Closed trail visiting at least three vertices

A closed trail cannot use bridges, because crossing a bridge would require crossing it back using the same edge again.

So we remove all bridges and check the bridge-free component containing vertex `1`.

If that component contains at least `3` vertices, then there is a closed trail through `1` visiting at least `3` vertices.

So `1` is possible.

---

### Bridge handling

Because the graph is a multigraph:

- an edge with multiplicity `>= 2` is never a bridge
- only edges with multiplicity exactly `1` can be bridges

We can find bridges using standard DFS / Tarjan algorithm on the simple version of the graph.

---

### Complexity

`N <= 100`, `M <= 1000`.

Using adjacency matrices and DFS/BFS, the solution is easily fast enough.

Overall complexity is roughly:

```text
O(N^3)
```

or better for these constraints.

---

## 4. C++ implementation with detailed comments

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

int n, m;

// g[a][b] = multiplicity of edge a-b.
vector<vector<int>> g;

/*
    BFS distances from source.
    dist[v] = shortest distance from src to v,
    or -1 if v is unreachable.
*/
vector<int> bfs_dist(int src) {
    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[src] = 0;
    q.push(src);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to = 1; to <= n; to++) {
            if (g[v][to] > 0 && dist[to] == -1) {
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }

    return dist;
}

/*
    Check whether dst is reachable from src
    in the current graph.
*/
bool reaches(int src, int dst) {
    vector<bool> vis(n + 1, false);
    queue<int> q;

    vis[src] = true;
    q.push(src);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to = 1; to <= n; to++) {
            if (g[v][to] > 0 && !vis[to]) {
                vis[to] = true;
                q.push(to);
            }
        }
    }

    return vis[dst];
}

/*
    Find bridges in the current multigraph.

    Important:
    - Parallel edges are never bridges.
    - Therefore only edges with multiplicity exactly 1
      can become bridges.

    bridge[a][b] == true means the single edge a-b is a bridge.
*/
vector<vector<bool>> find_bridges() {
    vector<vector<bool>> bridge(n + 1, vector<bool>(n + 1, false));

    // Build simple adjacency list: one neighbor entry if multiplicity > 0.
    vector<vector<int>> adj(n + 1);
    for (int a = 1; a <= n; a++) {
        for (int b = a + 1; b <= n; b++) {
            if (g[a][b] > 0) {
                adj[a].push_back(b);
                adj[b].push_back(a);
            }
        }
    }

    vector<int> tin(n + 1, 0), low(n + 1, 0);
    int timer = 0;

    function<void(int, int)> dfs = [&](int v, int parent) {
        tin[v] = low[v] = ++timer;

        for (int to : adj[v]) {
            if (to == parent) {
                continue;
            }

            if (tin[to] != 0) {
                // Back edge.
                low[v] = min(low[v], tin[to]);
            } else {
                dfs(to, v);
                low[v] = min(low[v], low[to]);

                // Edge v-to is a bridge only if:
                // 1. DFS condition says it is a bridge in the simple graph.
                // 2. There is exactly one copy of this edge.
                if (low[to] > tin[v] && g[v][to] == 1) {
                    bridge[v][to] = true;
                    bridge[to][v] = true;
                }
            }
        }
    };

    for (int v = 1; v <= n; v++) {
        if (tin[v] == 0) {
            dfs(v, 0);
        }
    }

    return bridge;
}

/*
    Check whether vertex v has at least one incident non-bridge edge.
    This is equivalent to saying that v lies on some cycle.
*/
bool has_cycle_through(int v, const vector<vector<bool>>& bridge) {
    for (int to = 1; to <= n; to++) {
        if (g[v][to] > 0 && !bridge[v][to]) {
            return true;
        }
    }
    return false;
}

/*
    Check whether vertex v belongs to a bridge-free component
    containing at least 3 vertices.

    This means there is a closed trail through v visiting
    at least 3 distinct vertices.
*/
bool in_large_bridge_free_component(int v) {
    vector<vector<bool>> bridge = find_bridges();

    vector<bool> vis(n + 1, false);
    queue<int> q;

    vis[v] = true;
    q.push(v);

    int cnt = 1;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int to = 1; to <= n; to++) {
            if (g[cur][to] > 0 && !bridge[cur][to] && !vis[to]) {
                vis[to] = true;
                cnt++;
                q.push(to);
            }
        }
    }

    return cnt >= 3;
}

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

    cin >> n >> m;

    g.assign(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        g[a][b]++;
        g[b][a]++;
    }

    vector<int> dist = bfs_dist(1);
    vector<int> answer;

    for (int u = 1; u <= n; u++) {
        // Unreachable vertices are impossible.
        if (dist[u] == -1) {
            continue;
        }

        if (u == 1) {
            /*
                We need to end at the start.
            */

            int degree_of_1 = 0;
            for (int w = 1; w <= n; w++) {
                degree_of_1 += g[1][w];
            }

            // If no edge touches 1, the ball never moves.
            if (degree_of_1 == 0) {
                answer.push_back(1);
                continue;
            }

            // Two-vertex oscillation using an even number of parallel edges.
            bool even_parallel = false;
            for (int w = 1; w <= n; w++) {
                if (g[1][w] >= 2 && g[1][w] % 2 == 0) {
                    even_parallel = true;
                    break;
                }
            }

            // Or a closed trail visiting at least three vertices.
            if (even_parallel || in_large_bridge_free_component(1)) {
                answer.push_back(1);
            }
        } else if (dist[u] >= 2) {
            /*
                There is a path 1 -> ... -> u with at least two edges.
                It visits at least three vertices, so it always works.
            */
            answer.push_back(u);
        } else {
            /*
                dist[u] == 1:
                u is directly adjacent to 1.
            */

            int x = g[1][u];

            // Temporarily remove all direct edges between 1 and u.
            g[1][u] = 0;
            g[u][1] = 0;

            bool ok = false;

            // If there is an alternative path, it visits at least 3 vertices.
            if (reaches(1, u)) {
                ok = true;
            }

            // If no alternative path, direct oscillation works when x is odd.
            if (!ok && x % 2 == 1) {
                ok = true;
            }

            /*
                If x is even, we need a cycle through 1 or u
                in the graph after removing direct edges.
            */
            if (!ok) {
                vector<vector<bool>> bridge = find_bridges();

                if (has_cycle_through(1, bridge) ||
                    has_cycle_through(u, bridge)) {
                    ok = true;
                }
            }

            // Restore direct edges.
            g[1][u] = x;
            g[u][1] = x;

            if (ok) {
                answer.push_back(u);
            }
        }
    }

    for (int i = 0; i < (int)answer.size(); i++) {
        if (i) cout << ' ';
        cout << answer[i];
    }
    cout << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
from collections import deque
import sys

sys.setrecursionlimit(1000000)


def main():
    data = list(map(int, sys.stdin.read().split()))

    n, m = data[0], data[1]

    # g[a][b] = multiplicity of edge a-b.
    g = [[0] * (n + 1) for _ in range(n + 1)]

    idx = 2
    for _ in range(m):
        a = data[idx]
        b = data[idx + 1]
        idx += 2

        g[a][b] += 1
        g[b][a] += 1

    def bfs_dist(src):
        """
        Compute shortest distances from src.
        dist[v] == -1 means unreachable.
        """
        dist = [-1] * (n + 1)
        q = deque([src])
        dist[src] = 0

        while q:
            v = q.popleft()

            for to in range(1, n + 1):
                if g[v][to] > 0 and dist[to] == -1:
                    dist[to] = dist[v] + 1
                    q.append(to)

        return dist

    def reaches(src, dst):
        """
        Return True if dst is reachable from src
        in the current graph.
        """
        visited = [False] * (n + 1)
        q = deque([src])
        visited[src] = True

        while q:
            v = q.popleft()

            for to in range(1, n + 1):
                if g[v][to] > 0 and not visited[to]:
                    visited[to] = True
                    q.append(to)

        return visited[dst]

    def find_bridges():
        """
        Find all bridges in the current multigraph.

        Parallel edges are never bridges, so an edge can be marked as a bridge
        only if its multiplicity is exactly 1.
        """
        bridge = [[False] * (n + 1) for _ in range(n + 1)]

        # Build simple adjacency list.
        adj = [[] for _ in range(n + 1)]
        for a in range(1, n + 1):
            for b in range(a + 1, n + 1):
                if g[a][b] > 0:
                    adj[a].append(b)
                    adj[b].append(a)

        tin = [0] * (n + 1)
        low = [0] * (n + 1)
        timer = 0

        def dfs(v, parent):
            nonlocal timer

            timer += 1
            tin[v] = low[v] = timer

            for to in adj[v]:
                if to == parent:
                    continue

                if tin[to] != 0:
                    # Back edge.
                    low[v] = min(low[v], tin[to])
                else:
                    dfs(to, v)
                    low[v] = min(low[v], low[to])

                    # Bridge condition in the simple graph,
                    # plus multiplicity check for the multigraph.
                    if low[to] > tin[v] and g[v][to] == 1:
                        bridge[v][to] = True
                        bridge[to][v] = True

        for v in range(1, n + 1):
            if tin[v] == 0:
                dfs(v, 0)

        return bridge

    def has_cycle_through(v, bridge):
        """
        Vertex v lies on a cycle iff it has an incident edge
        which is not a bridge.
        """
        for to in range(1, n + 1):
            if g[v][to] > 0 and not bridge[v][to]:
                return True
        return False

    def in_large_bridge_free_component(v):
        """
        Check whether v belongs to a bridge-free component
        with at least 3 vertices.
        """
        bridge = find_bridges()

        visited = [False] * (n + 1)
        q = deque([v])
        visited[v] = True

        count = 1

        while q:
            cur = q.popleft()

            for to in range(1, n + 1):
                if g[cur][to] > 0 and not bridge[cur][to] and not visited[to]:
                    visited[to] = True
                    count += 1
                    q.append(to)

        return count >= 3

    dist = bfs_dist(1)
    answer = []

    for u in range(1, n + 1):
        # If u is unreachable from 1, it is impossible.
        if dist[u] == -1:
            continue

        if u == 1:
            # We need a closed trail starting and ending at 1.

            degree_of_1 = sum(g[1][w] for w in range(1, n + 1))

            # If no swap touches vertex 1, the ball stays there.
            if degree_of_1 == 0:
                answer.append(1)
                continue

            # Check for an even positive multiplicity edge {1, w}.
            even_parallel = False
            for w in range(1, n + 1):
                if g[1][w] >= 2 and g[1][w] % 2 == 0:
                    even_parallel = True
                    break

            # Either a two-vertex oscillation works,
            # or a larger closed trail works.
            if even_parallel or in_large_bridge_free_component(1):
                answer.append(1)

        elif dist[u] >= 2:
            # A path of length at least 2 visits at least 3 vertices.
            answer.append(u)

        else:
            # dist[u] == 1, so u is directly adjacent to 1.

            x = g[1][u]

            # Temporarily remove all direct edges {1, u}.
            g[1][u] = 0
            g[u][1] = 0

            ok = False

            # Alternative path from 1 to u gives at least 3 visited vertices.
            if reaches(1, u):
                ok = True

            # If no alternative path, direct oscillation works iff x is odd.
            if not ok and x % 2 == 1:
                ok = True

            # If x is even, we need a cycle through 1 or through u.
            if not ok:
                bridge = find_bridges()

                if has_cycle_through(1, bridge) or has_cycle_through(u, bridge):
                    ok = True

            # Restore direct edges.
            g[1][u] = x
            g[u][1] = x

            if ok:
                answer.append(u)

    print(*answer)


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