#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
bool ok = 1;
vector<vll>adj;
vll res;
ll c[1005] = {0};
void solve(ll idx,ll p){
res.pb(idx+1);
bool f = 1;
ll posa = 0;
for(auto x:adj[idx]){
if(x != p){
if(f){
f = 0;
}
else{
res.pb(idx+1);
}
c[x] = c[idx] ^ 1;
solve(x,idx);
posa += adj[x].size() != 1;
}
}
if(posa > 1){
ok = 0;
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,m;
cin>>n>>m;
adj.assign(n+5,vll());
ll deg[n] = {0};
vector<ii>ed;
vll ans;
f(i,0,5000){
ans.pb(i);
}
f(i,0,m){
ll a,b;
cin>>a>>b;
a--;
b--;
deg[a]++;
deg[b]++;
ed.pb(ii(a,b));
}
ok = m == n-1;
vll w[n];
if(ok){
for(auto x:ed){
if(deg[x.F] != 1 && deg[x.S] != 1){
adj[x.F].pb(x.S);
adj[x.S].pb(x.F);
}
}
bool ivra = 0;
f(i,0,n){
f(j,0,5000){
w[i].pb(j);
}
}
f(i,0,n){
if(deg[i] != 1){
res.clear();
ok = 1;
solve(i,-1);
if(ok){
w[i] = res;
}
if(ok && res.size() < ans.size()){
ans = res;
}
ivra |= ok;
}
}
ok = ivra;
}
if(n == 1){
cout<<"YES\n";
cout<<"1\n 1\n";
}
else if(n == 2){
cout<<"YES\n";
cout<<"2\n2 2\n";
}
else if(ok){
cout<<"YES\n";
bool ek = 0;
f(i,0,n){
if(c[i] != c[ans[0]-1] && w[i].size() == ans.size()){
ek = 1;
break;
}
}
cout<<2 * ans.size() + (ek == 0)<<"\n";
for(auto x:ans){
cout<<x<<" ";
}
if(ans.size() % 2 == 0){
ek = 0;
f(i,0,n){
if(c[i] != c[ans[0]-1] && w[i].size() == ans.size()){
ans = w[i];
ek = 1;
break;
}
}
if(!ek){
ans.insert(ans.begin(),1);
}
}
for(auto x:ans){
cout<<x<<" ";
}
}
else{
cout<<"NO\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
