#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N = 1005;
const int mod = 1e6 + 7;
const int oo = 2e9;
const int M = 100050;
typedef long long ll;
typedef pair<int,int> pii;
vector <int> g[N];
int ng[N][N];
int sz[N];
int cnt;
int visi[N];
pii edges[M];
int curr[N];
int main() {
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
vector <vector<int>> dir(n, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
u--;v--;
dir[u][v] = dir[v][u] = 1;
g[u].pb(v);
g[v].pb(u);
edges[i] = {u, v};
}
for (int j = 0; j < n; ++j) {
vector <int> npss(n, 0);
npss[j] = 1;
for (auto &v : g[j]) npss[v] = 1;
for (int i = 0; i < n; ++i) sz[i] = 0, visi[i] = 0;
for (int dume = 0; dume < m; ++dume) {
auto &e = edges[dume];
if (npss[e.ff] || npss[e.ss]) continue;
ng[e.ff][sz[e.ff]++] = e.ss;
ng[e.ss][sz[e.ss]++] = e.ff;
}
cnt = 1;
for (int i = 0; i < n; ++i) {
if (npss[i] == 0 && !visi[i]) {
int curr_siz = 0;
curr[curr_siz++] = i;
visi[i] = cnt;
while (curr_siz > 0) {
int u = curr[curr_siz--];
for (int i = 0; i < sz[u]; ++i) {
int v = ng[u][i];
if (!visi[v] && npss[v] == 0) visi[v] = cnt, curr[curr_siz++] = v;
}
}
cnt++;
}
}
vector <vector<int>> incomp(n);
for (auto &v : g[j]) {
for (auto &v2 : g[v]) {
if (npss[v2] == 0) {
for (auto &h : incomp[visi[v2]]) {
if (!dir[h][v]) {
pii e = {v, j};
vector <int> npss2 (n, 0);
vector <int> di (n, oo);
vector <int> fat (n, -1);
npss2[e.ss] = 1;
for (auto &v : g[e.ss]) {
npss2[v] = 1;
}
queue <int> q;
q.push(e.ff);
di[e.ff] = 0;
while (q.size()) {
int u = q.front(); q.pop();
for (auto &v : g[u]) {
if (di[v] == oo) {
di[v] = di[u] + 1;
fat[v] = u;
if (npss2[v] == 0) q.push(v);
}
}
}
//cout << e.ff << " " << e.ss << "\n";
for (int i = 0; i < n; ++i) {
//cout << i << " " << npss[i] << " " << di[i] << '\n';
if (i != e.ff && npss2[i] && di[i] < oo && di[i] > 1) {
cout << e.ss + 1 << " ";
int cur = i;
while (cur != -1) {
cout << cur + 1 << " ";
cur = fat[cur];
}
cout << '\n';
return 0;
}
}
assert(h != e.ff && npss2[h] && di[h] < oo);
}
}
}
}
for (auto &v2 : g[v]) {
if (npss[v2] == 0) {
incomp[visi[v2]].pb(v);
}
}
}
}
cout << "no\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
4952 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5720 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
5724 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
9564 KB |
Output is correct |
| 2 |
Runtime error |
14 ms |
18760 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
19024 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
199 ms |
6740 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
