#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
random_device device;
default_random_engine rng(device());
//#define rand(l, r) uniform_int_distribution<ll> (l, r) (rng)
#define mp make_pair
#define IOS ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define FOR(i, j, n) for (int i = j; i<= n; i++)
#define ROF(i, n, j) for (int i = n; i>= j; i--)
#define pb push_back
#define sep cout << "--------" << endl;
#define S second
#define F first
#define all(a) a.begin(), a.end()
/*
#pragma GCC optimization("Ofast, unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("bmi")
#pragma GCC target("bmi2")
#pragma GCC target("lzcnt")
*/
const int mn = 20 + 5, mn2 = (1<<20) + 4;
int f[mn2], d[mn2];
vector<int> a[mn], A[mn2];
vector<pii> B[mn2];
queue<int> q;
int main()
{
IOS;
int n, m, u, v, w;
cin >> n;
m = n-1;
FOR(i, 1, m)
{
cin >> u >> v;
a[u].pb(v);
a[v].pb(u);
}
if (m != n-1)
{
cout << "NO";
return 0;
}
if (n == 1)
{
cout << "YES 1 1";
return 0;
}
if (n == 2)
{
cout << "YES 2 1 1";
return 0;
}
FOR(mask, 0, (1<<n)-1)
{
FOR(i, 1, n)
{
if ((mask&(1<<(i-1))))
{
for(auto v: a[i])
{
f[mask] = f[mask]|(1<<(v-1));
}
}
}
}
FOR(mask, 0, (1<<n)-1)
{
FOR(i, 1, n)
{
if ((mask&(1<<(i-1))))
{
A[f[mask-(1<<(i-1))]].pb(mask);
B[mask].pb(mp(f[mask-(1<<(i-1))], i));
}
}
}
d[0] = 0;
FOR(i, 1, (1<<n)-1)
{
d[i] = 1e9;
}
q.push(0);
bool flag = 0;
while (q.size())
{
int u = q.front();
q.pop();
for(auto v: A[u])
{
if (d[u]+1 < d[v])
{
d[v] = d[u]+1;
if (v == (1<<n)-1)
{
flag = 1;
break;
}
q.push(v);
}
}
if (flag) break;
}
if (d[(1<<n)-1] == 1e9)
{
cout << "NO";
//while (true) {}
return 0;
}
cout << "YES" << "\n" << 2*n - 4 << "\n";
u = (1<<n)-1;
while (u != 0)
{
for(auto p: B[u])
{
v = p.F;
w = p.S;
if (d[v] == d[u]-1)
{
cout << w << ' ';
u = v;
break;
}
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |