#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
void input(){
#define taskname ""
if(fopen(taskname ".inp", "r")){
freopen(taskname ".inp", "r", stdin);
freopen(taskname ".out","w",stdout);
}
}
const int N = 1e3+1;
const int INF =1e9+7;
ll n,m;
vector<vector<ll>>g(N);
vector<vector<ll>>col(N,vector<ll>(N,0));
vector<vector<pair<ll,ll>>>par(N,vector<pair<ll,ll>>(N));
void sub1(){
vector<vector<bool>>hw(n+1,vector<bool>(n+1,0));
for(ll i=0;i<m;++i){
ll u,v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
hw[u][v] = 1;
hw[v][u] = 1;
}
bool f =0;
// for(auto x : g[1]) cout << x << " ";
// cout << endl;
for(ll mask =0;mask < (1 << n);++mask){
if(__builtin_popcount(mask) < 4) continue;
vector<ll>pth;
for(ll i=1;i<=n;++i){
if((mask >> (i-1)) & 1) pth.push_back(i);
}
bool br = 0;
ll sz = pth.size();
for(ll i=0;i<pth.size();++i){
ll j = (i + 2) % sz;
while(1){
if(hw[pth[i]][pth[j]]){
br = 1;
break;
}
if(br) break;
++j;
j %= sz;
if(i == 0 && j == sz-1) break;
if(j == i-1) break;
}
if(br) break;
}
if(br) continue;
bool ck = 0;
vector<bool>vis(n+1,0);
ll i=0;
// for(auto x : pth) cout << x << " ";
// cout << endl;
while(1){
// cout << i << endl;
bool ok = 0;
for(auto x : g[pth[i]]){
// if(!ck) break;
if(x == pth[(i+1)%sz] && !vis[x]){
++i;
vis[x] = 1;
ok = 1;
break;
}
}
if(!ok) break;
if(i == sz){
ck = 1;
break;
}
}
if(ck){
f = 1;
for(auto x : pth) cout << x << " ";
cout << '\n';
break;
}
}
if(!f) cout << "no" << '\n';
}
bool dfs(pair<ll,ll> cur,vector<vector<vector<pair<ll,ll>>>>& g){
ll u = cur.first, v = cur.second;
col[u][v] = 1;
for(auto x : g[u][v]){
ll u1 = x.first, v1 = x.second;
if(col[u1][v1] == 0){
par[u1][v1] = {u,v};
if(dfs(x,g)) return 1;
}
else if(col[u1][v1] == 1) return 1;
}
col[u][v] = 2;
return 0;
}
void sub4(){
vector<unordered_set<int>> adj(n+1);
vector<pair<int,int>> ed;
ed.reserve(m);
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
adj[u].insert(v);
adj[v].insert(u);
ed.push_back({u, v});
}
vector<pair<int,int>> canh;
for(auto &e : ed){
canh.push_back({e.first, e.second});
canh.push_back({e.second, e.first});
}
int sz = canh.size();
vector<vector<int>> pos(n+1);
for(int i = 0; i < sz; ++i) pos[canh[i].first].push_back(i);
vector<vector<int>> g(sz);
for(int i = 0; i < sz; ++i){
int u = canh[i].first;
int v = canh[i].second;
for(int jid : pos[v]){
int w = canh[jid].second;
if(w == u) continue;
if(adj[u].count(w) == 0) g[i].push_back(jid);
}
}
vector<int> col(sz, 0), par(sz, -1);
bool kt = 0;
vector<int> ct;
for(int s = 0; s < sz && !kt; ++s){
if(col[s] != 0) continue;
vector<pair<int,int>> stk;
stk.push_back({s, 0});
col[s] = 1;
par[s] = -1;
while(!stk.empty() && !kt){
int node = stk.back().first;
int &it = stk.back().second;
if(it < g[node].size()){
int to = g[node][it++];
if(col[to] == 0){
par[to] = node;
col[to] = 1;
stk.push_back({to, 0});
}
else if(col[to] == 1){
vector<int> idxs;
int cur = node;
idxs.push_back(cur);
while(cur != to){
cur = par[cur];
if(cur == -1) break;
idxs.push_back(cur);
}
if(cur == -1) continue;
reverse(idxs.begin(), idxs.end());
vector<int> ans;
ans.push_back(canh[idxs[0]].first);
for(int t = 0; t < idxs.size(); ++t) ans.push_back(canh[idxs[t]].second);
if(ans.size() > 1 && ans.front() == ans.back()) ans.pop_back();
if(ans.size() >= 4){
unordered_set<int> seen;
bool ok = true;
for(int x : ans){
if(seen.count(x)){
ok = false;
break;
}
seen.insert(x);
}
if(ok){
ct = ans;
kt = true;
break;
}
}
}
}
else{
col[node] = 2;
stk.pop_back();
}
}
}
if(!kt){
cout << "no";
return;
}
for(int i = 0; i < ct.size(); ++i) cout << ct[i] << ' ';
}
int main(){
cin.tie(0)->sync_with_stdio(0);
input();
cin >> n >> m;
//if(n <= 1 && m <= 45) sub1();
//else sub4();
sub4();
return 0;
}
/*
4 5
1 2
2 3
3 4
4 1
1 3
*/
Compilation message (stderr)
indcyc.cpp: In function 'void input()':
indcyc.cpp:10:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen(taskname ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:11:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | freopen(taskname ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |