#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,p[5009],pi,kl[1003][1003],DP[1009],l[5009],li,bo[5009],P[5009],PI;
int CH[1009][1009];
vector <int> v[1009];
void print(){
pi=PI;
for(i=1; i<=PI; i++){
p[i]=P[i];
}
cout<<"YES\n";
cout<<pi<<"\n";
for(i=1; i<=pi; i++){
cout<<p[i]<<" ";
}
/*
cout<<"\n";
for(i=1; i<=a; i++) CH[0][i]=1;
for(j=1; j<=pi; j++){
for(i=1; i<=a; i++){
CH[j][i]=0;
for(vector <int>::iterator it=v[i].begin(); it!=v[i].end(); it++){
if(p[j]!=(*it)&&CH[j-1][(*it)]==1){
CH[j][i]=1;break;
}
}
}
}
e=0;
for(i=1; i<=a; i++){
if(CH[pi][i]==1) e++;
}
cout<<"WRONG: "<<e;
*/
exit(0);
}
void dfs(int q, int w, int rr){
e=max(e,rr);
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
dfs((*it),q,rr+1);
}
}
void dfs2(int q, int w){
int I=i;
li++;l[li]=q;bo[q]=1;
if(DP[q]-kl[q][w]==0){
pi=0;
for(j=1; j<=li; j++){
pi++;p[pi]=l[j];
for(vector <int>::iterator it=v[l[j]].begin(); it!=v[l[j]].end(); it++){
if(bo[(*it)]==1) continue;
if(v[(*it)].size()!=1){
pi++;p[pi]=(*it);
pi++;p[pi]=l[j];
}
}
}
for(i=pi; i>=1; i--){
pi++;p[pi]=p[i];
}
if(PI>pi){
PI=pi;
for(i=1; i<=pi; i++) P[i]=p[i];
}
i=I;
//print();
}
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
if(DP[q]-kl[q][w]-kl[q][(*it)]>0) continue;
dfs2((*it),q);
}
li--;bo[q]=0;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;PI=10*a+10;
for(i=1; i<=b; i++){
cin>>c>>d;
v[c].push_back(d);
v[d].push_back(c);
}
if(a==1){
pi=1;p[1]=1;
print();
}
if(a==2){
pi=2;p[1]=1;p[2]=1;
print();
}
if(b!=a-1){
cout<<"NO";
return 0;
}
for(i=1; i<=a; i++){
for(vector <int>::iterator it=v[i].begin(); it!=v[i].end(); it++){
e=0;
dfs((*it),i,1);
if(e>2){
kl[i][(*it)]=1;DP[i]++;
}
}
}
for(i=1; i<=a; i++){
dfs2(i,0);
}
if(PI!=10*a+10){
print();
}
cout<<"NO";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Integer parameter [name=k] equals to 20, violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Integer parameter [name=k] equals to 20, violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Integer parameter [name=k] equals to 20, violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
