#include <bits/stdc++.h>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;
// How interesting!
int n, m, t;
vector<int> adj[N];
int low[N], tim[N];
void dfs(int x, int p)
{
low[x] = tim[x] = ++t;
for (auto u : adj[x])
{
if (u == p)
continue;
if (low[u])
{
low[x] = min(low[x], tim[u]);
}
else
{
dfs(u, x);
low[x] = min(low[x], low[u]);
}
if (low[u] > tim[x])
{
cout << x << " " << u << "\n";
}
}
}
struct dsu
{
int fat[N];
dsu()
{
for (int i = 0; i < N; ++i)
fat[i] = i;
}
int find(int x) { return (x == fat[x] ? x : find(fat[x])); }
void link(int u, int v)
{
u = find(u);
v = find(v);
if (u != v)
{
fat[u] = v;
}
}
bool same(int u, int v)
{
return find(u) == find(v);
}
} d1, d2;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("in.in", "r", stdin);
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int u, v;
cin >> u >> v;
if (!d1.same(u, v))
{
d1.link(u, v);
}
else if (!d2.same(u, v))
{
d2.link(u, v);
}
// else
// continue;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; ++i)
{
if (!tim[i])
dfs(i, i);
}
return 0;
}
/*
- bounds sir (segtree = 4N, eulerTour = 2N, ...)
- a variable defined twice?
- will overflow?
- is it a good complexity?
- don't mess up indices (0-indexed vs 1-indexed)
- reset everything between testcases.
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3456 KB |
Too short sequence |
2 |
Incorrect |
3 ms |
3456 KB |
Wrong answer on graph without induced cycle |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3456 KB |
Too short sequence |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3448 KB |
Too short sequence |
2 |
Incorrect |
3 ms |
3456 KB |
Unexpected end of file - token expected |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3456 KB |
Too short sequence |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3456 KB |
Too short sequence |
2 |
Incorrect |
3 ms |
3456 KB |
Unexpected end of file - token expected |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
3584 KB |
Wrong answer on graph without induced cycle |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3584 KB |
Too short sequence |
2 |
Incorrect |
6 ms |
3584 KB |
Unexpected end of file - token expected |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
4216 KB |
Too short sequence |
2 |
Correct |
12 ms |
3968 KB |
Too short sequence |
3 |
Incorrect |
41 ms |
4472 KB |
Wrong answer on graph without induced cycle |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
3960 KB |
Too short sequence |
2 |
Incorrect |
77 ms |
3832 KB |
Unexpected end of file - token expected |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
4600 KB |
Too short sequence |
2 |
Incorrect |
221 ms |
4664 KB |
Unexpected end of file - token expected |
3 |
Halted |
0 ms |
0 KB |
- |