Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef int64_t ll;
- #define For(i, a, b) for(ll i = a; i <= b; i++)
- ll n, m, valid, num[100010];
- vector <ll> edge[100010], res;
- void dfs(ll u)
- {
- for(ll v: edge[u])
- if (edge[v].size() > 1 && !num[v])
- {
- num[v] = num[u] + 1;
- dfs(v);
- if (valid && *res.end() != *res.begin())
- {
- res.push_back(v);
- return;
- }
- num[v] = 0;
- }
- else
- if (num[u] - num[v] > 2 && res.empty())
- {
- valid = v;
- res.push_back(v);
- res.push_back(u);
- return;
- }
- }
- void process()
- {
- For(i, 1, n)
- if (!num[i] && res.empty())
- {
- num[i] = 1;
- dfs(i);
- }
- if (res.empty())
- cout << "IMPOSSIBLE" << "\n";
- else
- {
- cout << res.size() << "\n";
- reverse(res.begin(), res.end());
- for(ll v: res)
- cout << v << ' ';
- }
- }
- void input()
- {
- cin >> n >> m;
- For(i, 1, m)
- {
- ll u, v;
- cin >> u >> v;
- edge[u].push_back(v);
- edge[v].push_back(u);
- }
- }
- int main()
- {
- /* freopen("test.in", "r", stdin);
- freopen("test.ok", "w", stdout); */
- input();
- process();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement