//khodaya khodet komak kon
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
# define fast_io ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 1e3 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;
int n, m, H[xn], rt1, rt2, P[xn];
vector <int> adj[xn], masir, vec, ans;
bool mark[xn], flag;
void DFS(int v, int p = - 1){
P[v] = p;
mark[v] = true;
for (int u : adj[v]){
if (mark[u]){
flag |= u != p;
continue;
}
H[u] = H[v] + 1;
DFS(u, v);
}
}
void DFS2(int v, int p = - 1){
flag |= 2 < H[v];
for (int u : adj[v]){
if (mark[u] || u == p)
continue;
if (mark[v] && 1 < SZ(adj[u])){
vec.push_back(v);
vec.push_back(u);
}
H[u] = H[v] + 1;
DFS2(u, v);
}
}
int main(){
fast_io;
cin >> n >> m;
for (int i = 1; i <= m; ++ i){
int v, u;
cin >> v >> u;
adj[v].push_back(u);
adj[u].push_back(v);
}
if (n <= 2){
cout << "YES\n";
cout << n << endl;
for (int i = 1; i <= n; ++ i)
cout << 1 << sep;
cout << endl;
return 0;
}
DFS(1);
if (flag)
kill("NO");
for (int i = 1; i <= n; ++ i)
if (H[rt1] < H[i])
rt1 = i;
H[rt1] = 0;
fill(mark, mark + n + 1, false);
DFS(rt1);
for (int i = 1; i <= n; ++ i)
if (H[rt2] < H[i])
rt2 = i;
fill(mark, mark + n + 1, false);
rt2 = P[rt2];
while (rt2 != rt1){
masir.push_back(rt2);
rt2 = P[rt2];
}
for (int v : masir)
mark[v] = true;
for (int v : masir){
vec.push_back(v);
H[v] = 0;
DFS2(v);
if (flag)
kill("NO");
}
for (int x : vec)
ans.push_back(x);
reverse(all(vec));
for (int x : vec)
ans.push_back(x);
cout << SZ(ans) << endl;
for (int x : ans)
cout << x << sep;
cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Token "6" doesn't correspond to pattern "YES|NO" |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Token "2" doesn't correspond to pattern "YES|NO" |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Token "6" doesn't correspond to pattern "YES|NO" |
| 4 |
Halted |
0 ms |
0 KB |
- |
