#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;
int par[1023],dep[1023],pari[1023];
vector<int>a[2][2];
void cal(int pos){
dep[pos]=0;
for(int x:komsu[pos]){
if(par[pos]==x)continue;
pari[x]=pari[pos]^1;
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(dep[x]==0)break;
if(!dfs(x))return false;
if(par[pos]==0&&child.size()==1)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 t=(komsu[root].size()==1)^((pari[root]&1)^(pari[1]&1));
if(a[1][t].size()==0||a[1][t].size()>ans.size()){
a[1][t]=ans;
}
if(a[1][t^1].size()==0||a[1][t^1].size()>ans.size()+1){
a[1][t^1]=ans;
a[1][t^1].pb(1);
}
t^=(int(ans.size())&1)^1;
if(a[0][t].size()==0||a[0][t].size()>ans.size()){
a[0][t]=ans;
}
if(a[0][t^1].size()==0||a[0][t^1].size()>ans.size()+1){
a[0][t^1]=ans;
a[0][t^1].pb(1);
}
}
ans.clear();
}
if(a[0][0].size()){
cout<<"YES"<<endl;
int x=a[0][0].size()+a[1][0].size(),y=a[0][1].size()+a[1][1].size();
if(x<y){
cout<<x<<endl;
for(int c:a[1][0]){
cout<<c<<" ";
}
for(int c:a[0][0]){
cout<<c<<" ";
}
cout<<endl;
}
else{
cout<<y<<endl;
for(int c:a[1][1]){
cout<<c<<" ";
}
for(int c:a[0][1]){
cout<<c<<" ";
}
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... |