p270.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<vector<int>> g;

void read() {
    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]++;
    }
}

bool reaches(int src, int dst) {
    vector<bool> vis(n + 1, false);
    queue<int> q;
    q.push(src);
    vis[src] = true;
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int w = 1; w <= n; w++) {
            if(g[v][w] > 0 && !vis[w]) {
                vis[w] = true;
                q.push(w);
            }
        }
    }

    return vis[dst];
}

vector<int> bfs_dist(int src) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(src);
    dist[src] = 0;
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int w = 1; w <= n; w++) {
            if(g[v][w] > 0 && dist[w] == -1) {
                dist[w] = dist[v] + 1;
                q.push(w);
            }
        }
    }

    return dist;
}

bool has_cycle_through(int v) {
    for(int z = 1; z <= n; z++) {
        if(z == v || g[v][z] == 0) {
            continue;
        }

        g[v][z]--;
        g[z][v]--;

        bool ok = reaches(v, z);

        g[v][z]++;
        g[z][v]++;

        if(ok) {
            return true;
        }
    }

    return false;
}

bool in_large_2ec(int v) {
    vector<vector<bool>> bridge(n + 1, vector<bool>(n + 1, false));
    for(int a = 1; a <= n; a++) {
        for(int b = a + 1; b <= n; b++) {
            if(g[a][b] != 1) {
                continue;
            }

            g[a][b] = g[b][a] = 0;
            bool reach = reaches(a, b);
            g[a][b] = g[b][a] = 1;

            if(!reach) {
                bridge[a][b] = bridge[b][a] = true;
            }
        }
    }

    vector<bool> vis(n + 1, false);
    queue<int> q;
    q.push(v);
    vis[v] = true;
    int cnt = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int w = 1; w <= n; w++) {
            if(g[u][w] > 0 && !bridge[u][w] && !vis[w]) {
                vis[w] = true;
                cnt++;
                q.push(w);
            }
        }
    }

    return cnt >= 3;
}

void solve() {
    // The M swaps form an undirected multigraph G on vertices 1...N. Whatever
    // ordering we pick, the ball traces a trail in G (an edge-disjoint walk):
    // a swap whose two positions include the ball moves it across that edge,
    // every other swap leaves the ball stationary. Conversely, given any
    // trail T from 1 to u with vertex set S(T), we can realise it as a full
    // ordering iff every edge {x,y} not in T can be slipped into some phase
    // where the ball sits at a vertex of S(T) outside {x,y}, i.e. iff
    // S(T) \ {x,y} is non-empty for every non-trail edge.
    //
    // This is automatic whenever |S(T)| >= 3, because no pair {x,y} can cover
    // three vertices. So position u is reachable as soon as we can produce a
    // trail from 1 to u that visits at least three distinct vertices, and the
    // hard cases are |S(T)| <= 2:
    //
    //   - dist[u] >= 2: the BFS shortest path is itself a trail with
    //     |S| >= 3, so u is reachable.
    //
    //   - dist[u] == 1 (a direct {1,u} edge exists): let x = mult({1,u}) and
    //     drop all {1,u} edges to form G'. If 1 still reaches u in G', the
    //     alternate path has length >= 2 and combined with a direct edge
    //     yields a |S| >= 3 trail. Otherwise the trail can only cross the
    //     {1,u} bridge through direct edges. Using all x of them oscillating
    //     ends at u iff x is odd, and that |S|=2 trail works because every
    //     other edge has at least one endpoint outside {1,u}. If x is even
    //     we must enrich the oscillation with a closed walk on a third
    //     vertex on either side, which exists iff 1 lies on a cycle in G'
    //     or u lies on a cycle in G' (multi-edges count, since we will glue
    //     a final direct {1,u} edge that already adds the third vertex).
    //
    //   - u == 1: we need a closed trail at 1 that absorbs every other edge.
    //     The empty trail handles degree(1) == 0; an oscillation on a
    //     multi-edge {1,w} of even multiplicity >= 2 handles |S| = 2 (every
    //     other edge has at least one endpoint outside {1,w}); and a closed
    //     trail visiting at least three distinct vertices handles |S| >= 3.
    //     A closed trail at 1 visiting >= 3 vertices exists iff 1 lies in a
    //     2-edge-connected component of size >= 3, which is *not* the same
    //     as 1 being on a simple cycle of >= 3 vertices: the trail may
    //     revisit a vertex (e.g. 1->2->3->2->1 in {1,2}*3 + {2,3}*2 reuses
    //     vertex 2 with edge-disjoint multi-edge pairs). We compute it by
    //     finding bridges -- single-multiplicity edges whose removal
    //     disconnects their endpoints -- and BFSing in the bridge-free
    //     subgraph, counting the vertices reachable from 1.
    //
    // Cycle-through-v in the dist[u] == 1 case allows multi-edges and is a
    // simple "remove one {v,z} edge, BFS, did we still reach z" check; it is
    // sufficient there because the final direct {1,u} edge already provides
    // the third vertex.

    vector<int> dist = bfs_dist(1);
    vector<int> ans;
    for(int u = 1; u <= n; u++) {
        if(dist[u] == -1) {
            continue;
        }

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

            if(deg == 0) {
                ans.push_back(u);
                continue;
            }

            bool even_multi = false;
            for(int w = 1; w <= n; w++) {
                if(g[1][w] >= 2 && g[1][w] % 2 == 0) {
                    even_multi = true;
                    break;
                }
            }

            if(even_multi || in_large_2ec(1)) {
                ans.push_back(u);
            }
        } else if(dist[u] >= 2) {
            ans.push_back(u);
        } else {
            int x = g[1][u];
            g[1][u] = g[u][1] = 0;
            bool ok = reaches(1, u);
            if(!ok && x % 2 == 1) {
                ok = true;
            }

            if(!ok && (has_cycle_through(1) || has_cycle_through(u))) {
                ok = true;
            }

            g[1][u] = g[u][1] = x;
            if(ok) {
                ans.push_back(u);
            }
        }
    }

    cout << ans << '\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;
}

=================
p270.in1
======================
4 3
1 2
1 2
2 3

=================
p270.ans1
======================
1 3

=================
statement.txt
======================
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

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