#include <bits/stdc++.h>
using namespace std;
#define TOF_IO ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define File_IO(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
#define SEP ' '
#define endl '\n'
#define Set_Prec(k, x) cout << fixed << setprecision(k) << x << '\n';
#define BSearch(first, second, t) lower_bound(arr, arr+n, t)-arr
#define F first
#define S second
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
#define EDGE(arr, x, y) arr[x].PB(y), arr[y].PB(x)
typedef int ll;
typedef long double lld;
const ll M = 1e9+7;
//const ll IM = 1e18 + 37;
//ll POW(ll a, ll b, ll md); ll GCD(ll a, ll b); ll LCM(ll a, ll b); int lis(std::vector<int>& v);
/*
ll factI[N + 1], Numi[N + 1], fact[N + 1];
void InverseofNumber(ll p = M); void InverseofFactorial(ll p = M); void factorial(ll p = M); ll nPr(ll N, ll R, ll p = M); ll nCr(ll N, ll R, ll p = M); void comb();
*/
const ll N = 1e5 + 10;
ll n, m, x, y, z, par[N], H[N], BE[N], par2[N];
bool seen[N], ans[N];
vector<ll> G1[N];
ll getPar(ll v)
{
return (par[v] == v? v : par[v] = getPar(par[v]));
}
ll getPar2(ll v)
{
return (par2[v] == v? v : par2[v] = getPar2(par2[v]));
}
void Union(ll v, ll u)
{
v = getPar(v); u = getPar(u);
par[v] = u;
}
void Union2(ll v, ll u)
{
v = getPar2(v); u = getPar2(u);
par2[v] = u;
}
void Im_fucking_tired()
{
for(int i=0; i<N; i++)
{
par[i] = i;
par2[i] = i;
}
}
void dfs(ll v, ll fad)
{
seen[v] = 1;
for(auto u: G1[v])
{
if(!seen[u])
{
H[u] = H[v] + 1;
BE[u] = H[u];
dfs(u, v);
BE[v] = min(BE[v], BE[u]);
//cout << BE[u] << SEP << H[u] << endl;
if(BE[u] < H[u]) continue;
if(count(ALL(G1[v]), u) == 1) cout << v << SEP << u << endl;
}
else
{
if(u == fad)
{
continue;
}
BE[v] = min(BE[v], H[u]);
}
}
}
/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** ------------------------------------------------------------------------------SOLVE-----------------------------------------------------------------------------------------***/
/* _______________________________________________________________________________________________________________________________________________________________________________*/
void solve()
{
Im_fucking_tired();
cin >> n >> m;
ll cnt = 0;
for(int i=1; i<=m; i++, cnt++)
{
cin >> x >> y;
if(x > y) swap(x, y);
if(getPar(x) != getPar(y))
{
Union(x, y);
EDGE(G1, x, y);
}
else if(getPar2(x) != getPar2(y))
{
Union2(x, y);
EDGE(G1, x, y);
}
}
for(int i=1; i<=n; i++)
{
if(!seen[i]) H[i] = 1, dfs(i, -1);
}
}
/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** -------------------------------------------------------------------------------MAIN-----------------------------------------------------------------------------------------***/
/* _______________________________________________________________________________________________________________________________________________________________________________*/
int main()
{
//File_IO("input.txt", "output.txt");
TOF_IO;
ll t=1;
//cin >> t;
for(int k=0; k<t; k++)
{
solve();
}
return 0;
}
/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** ---------------------------------------------------------------------------FUNCTIONS----------------------------------------------------------------------------------------***/
/* _______________________________________________________________________________________________________________________________________________________________________________*/
/*
void InverseofNumber(ll p = M){Numi[0] = Numi[1] = 1; for (ll i = 2; i <= N; i++){Numi[i] = Numi[p % i] * (p - p / i) % p;}}
void InverseofFactorial(ll p = M){factI[0] = factI[1] = 1;for (ll i = 2; i <= N; i++){factI[i] = (Numi[i] * factI[i - 1]) % p;}}
void factorial(ll p = M){fact[0] = 1;for (ll i = 1; i <= N; i++){fact[i] = (fact[i - 1] * i) % p;}}
ll nPr(ll N, ll R, ll p = M){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N]) % p * factI[N - R]) % p;return ans;}
ll nCr(ll N, ll R, ll p = M){if (N - R < 0 || R < 0) {return 0};int ans = ((fact[N] * factI[R]) % p * factI[N - R]) % p;return ans;}
void comb(){ll p = M;InverseofNumber(p);InverseofFactorial(p);factorial(p);}
*/
ll POW(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * POW(a * a % md, b / 2, md) % md : POW(a * a % md, b / 2, md) % md));}
//ll GCD(ll a, ll b) {return b?GCD(b,a%b):a;}
//ll LCM(ll a, ll b) {return a/GCD(a,b)*b;}
//int lis(std::vector<int>& v){if (v.size() == 0) {return 0;} vector<int> tail(v.size(), 0); int length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3924 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
3848 KB |
Output is correct |
| 2 |
Correct |
79 ms |
3588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
4472 KB |
Output is correct |
| 2 |
Correct |
159 ms |
3960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
241 ms |
6220 KB |
Output is correct |
| 2 |
Correct |
195 ms |
5704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
356 ms |
11552 KB |
Output is correct |
| 2 |
Correct |
282 ms |
7508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
494 ms |
12832 KB |
Output is correct |
| 2 |
Correct |
472 ms |
9520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
669 ms |
14992 KB |
Output is correct |
| 2 |
Correct |
621 ms |
9260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
805 ms |
14996 KB |
Output is correct |
| 2 |
Correct |
752 ms |
9304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
958 ms |
14404 KB |
Output is correct |
| 2 |
Correct |
922 ms |
11224 KB |
Output is correct |
