#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
int n,m;
vector<int>komsu[1023];
vector<int>ans;
vector<int>anss;
int par[1023],dep[1023];
void cal(int pos){
dep[pos]=0;
for(int x:komsu[pos]){
if(par[pos]==x)continue;
par[x]=pos;
cal(x);
dep[pos]=max(dep[pos],dep[x]+1);
}
}
bool dfs(int pos){
vector<int>child;
for(int x:komsu[pos]){
if(par[pos]==x)continue;
child.pb(x);
}
sort(child.begin(),child.end(),[&](const int &x,const int &y){
return dep[x]>dep[y];
});
if(child.size()==0)return true;
if(child.size()>1){
if(dep[child[1]]>1)return false;
}
if(dep[child[0]]==0){
ans.pb(pos);
return true;
}
for(int x:child){
if(!dfs(x))return false;
if(dep[x]==0)break;
ans.pb(pos);
}
return true;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;cin>>x>>y;
komsu[x].pb(y);
komsu[y].pb(x);
}
if(m!=n-1){
cout<<"NO"<<endl;
return 0;
}
if(n<=2){
cout<<"YES"<<endl<<n<<endl;
for(int i=0;i<n;i++){
cout<<"1 ";
}
cout<<endl;
return 0;
}
for(int root=1;root<=n;root++){
par[root]=0;
cal(root);
if(dfs(root)){
int s=ans.size();
if((dep[ans[0]]&1)!=(dep[root]&1))ans.pb(ans[0]);
for(int i=0;i<s;i++){
ans.pb(ans[i]);
}
if(anss.size()==0||anss.size()>ans.size()){
swap(ans,anss);
}
}
ans.clear();
}
if(anss.size()){
cout<<"YES"<<endl<<anss.size()<<endl;
for(int x:anss)
cout<<x<<" ";
cout<<endl;
}
else cout<<"NO"<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |