#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
bool vis[1001];
int par[1001],depth[1001],n;
vector<int>adj[1000];
void dfs1(int v,int u){
for(int x:adj[v]){
if(x == u)continue;
depth[x] = depth[v]+1;
par[x] = v;
dfs1(x,v);
}
}
int search(int s){
for(int i=1;i<=n;i++)depth[i] = 0;
dfs1(s,-1);
int mx = 0;
int res = 0;
for(int i=1;i<=n;i++)if(depth[i] > mx){mx=depth[i],res=i;}
return res;
}
void no(){
cout<<"NO";
exit(0);
}
bool inpath[1000];
bool check(int v,int u,int dep){
if(dep>=3)return 1;
for(int x:adj[v]){
if(x==u || inpath[x])continue;
if(check(x,v,dep+1))return 1;
}
return 0;
}
int main()
{
int m;
cin>>n>>m;
for(int i=0;i<m;i++){
int v,u;
cin>>v>>u;
adj[v].pb(u);
adj[u].pb(v);
}
if(n<=2){
cout<<"YES"<<'\n';
cout<<2<<'\n';
cout<<"1 1"<<'\n';
}
if(m>=n)no();
int s = search(1);
int t = search(s);
vector<int>path;
while(true){
inpath[t] = 1;
path.pb(t);
if(t==s)break;
t = par[t];
}
reverse(all(path));
vector<int>ans;
for(int i=1;i+1<sz(path);i++){
int v = path[i];
ans.pb(v);
if(check(v,0,0))no();
for(int x:adj[v]){
ans.pb(x);
ans.pb(v);
}
}
int k = sz(ans);
for(int i=k-1;i>=0;i--)ans.pb(ans[i]);
cout<<"YES"<<'\n';
cout<<sz(ans)<<'\n';
for(int x:ans)cout<<x<<" ";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
