#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define long unsigned long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
const int N = 1e3+3;
vector <int> graph[N];
int depth[N], furthest[N];
vector <int> diameter, tmp;
int df, vf, in_diameter[N];
void find_furthest(int v, int p, int dist) {
tmp.pb(v);
if (dist > df) {
df = dist;
vf = v;
diameter = tmp;
}
for (auto to : graph[v]) {
if (to == p) continue;
find_furthest(to, v, dist+1);
}
tmp.pop_back();
}
int dfs(int v, int p) {
int mx = depth[v];
for (auto to : graph[v]) {
if (to == p || in_diameter[to]) continue;
depth[to] = depth[v] + 1;
mx = max(mx, dfs(to, v));
}
furthest[v] = mx;
return mx;
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
graph[a].pb(b);
graph[b].pb(a);
}
find_furthest(1, 1, 0);
df = 0;
find_furthest(vf, vf, 0);
df = 0;
for (auto to : diameter) in_diameter[to] = 1;
for (int i = 0; i < sz(diameter); i++) {
auto to = diameter[i];
dfs(to, to);
if (furthest[to] >= 3 && i >= 3 && i <= n-4) {
df++;
}
}
if (m >= n || df) {
cout << "NO" << endl;
return;
}
vector <int> order;
for (int i = 1; i < sz(diameter)-1; i++) {
order.pb(diameter[i]);
for (auto to : graph[diameter[i]]) {
if (to == diameter[i+1] || to == diameter[i-1] || sz(graph[to]) == 1) continue;
order.pb(to);
order.pb(diameter[i]);
}
}
cout << "YES" << endl;
if (n == 1) {
cout << "1\n1";
return;
}
else if (n == 2) {
cout << "2\n1 1";
return;
}
cout << sz(order)*2 << endl;
for (auto to : order) cout << to << ' ';
for (auto to : order) cout << to << ' ';
}
int main() {
do_not_disturb
int t = 1;
//~ cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
12 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 9
9 10
10 11
5 12
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Partially correct |
0 ms |
340 KB |
Failed to provide a successful strategy. |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Partially correct |
0 ms |
340 KB |
Failed to provide a successful strategy. |
7 |
Execution timed out |
1093 ms |
7628 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Partially correct |
0 ms |
340 KB |
Failed to provide a successful strategy. |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Partially correct |
0 ms |
340 KB |
Failed to provide a successful strategy. |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Partially correct |
1 ms |
340 KB |
Failed to provide a successful strategy. |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Partially correct |
0 ms |
340 KB |
Failed to provide a successful strategy. |
11 |
Partially correct |
1 ms |
468 KB |
Failed to provide a successful strategy. |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Partially correct |
1 ms |
468 KB |
Failed to provide a successful strategy. |
14 |
Partially correct |
1 ms |
468 KB |
Failed to provide a successful strategy. |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Partially correct |
1 ms |
468 KB |
Failed to provide a successful strategy. |
17 |
Correct |
1 ms |
480 KB |
Output is correct |
18 |
Partially correct |
1 ms |
468 KB |
Failed to provide a successful strategy. |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Partially correct |
1 ms |
468 KB |
Failed to provide a successful strategy. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Partially correct |
0 ms |
340 KB |
Failed to provide a successful strategy. |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Partially correct |
0 ms |
340 KB |
Failed to provide a successful strategy. |
7 |
Execution timed out |
1093 ms |
7628 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |