#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<pair<ll, ll>> G1[N];
vector<pair<ll, ll>> E;
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)
{
seen[v] = 1;
for(auto p: G1[v])
{
ll u = p.F, e = p.S;
if(!seen[u])
{
H[u] = H[v] + 1;
BE[u] = H[u];
dfs(u);
BE[v] = min(BE[v], BE[u]);
//cout << BE[u] << SEP << H[u] << endl;
if(BE[u] < H[u]) ans[e] = 1;
}
else
{
if(H[v] <= H[u]+1) continue;
BE[v] = min(BE[v], H[u]);
if(H[v] > H[u] + 1)ans[e] = 1;
}
}
}
/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** ------------------------------------------------------------------------------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);
G1[y].PB({x, cnt});
G1[x].PB({y, cnt});
E.PB({min(x, y), max(x, y)});
}
else if(getPar2(x) != getPar2(y))
{
Union2(x, y);
G1[y].PB({x, cnt});
G1[x].PB({y, cnt});
E.PB({min(x, y), max(x, y)});
}
else
{
cnt--;
}
}
for(int i=1; i<=n; i++)
{
if(!seen[i]) H[i] = 1, dfs(i);
}
//cout << H[9] << SEP << H[10] << SEP << BE[9] << SEP << BE[10] << endl;
vector<pair<bool, pair<ll, ll>>> anss;
for(int i=0; i<cnt; i++)
{
if(ans[i] == 0 or 1)
{
anss.PB({ans[i], E[i]});
}
}
sort(ALL(anss));
vector<pair<ll, ll>> Fuck;
if(anss.size() == 1 or anss[0].S != anss[1].S) if(!anss[0].F)Fuck.PB(anss[0].S);
for(int i=1; i<int(anss.size())-1; i++)
{
if(anss[i].S != anss[i-1].S && anss[i].S != anss[i+1].S) if(!anss[i].F)Fuck.PB(anss[i].S);
}
if(anss.size() != 1 and anss[anss.size()-1].S != anss[anss.size()-2].S) if(!anss[anss.size()-1].F)Fuck.PB(anss[anss.size()-1].S);
for(auto fff: Fuck)
{
cout << fff.F << SEP << fff.S << endl;
}
}
/* _________________________________________________________________________________________________________________________________________________________________________________*/
/*** -------------------------------------------------------------------------------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 |
Incorrect |
2 ms |
3412 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4308 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
4124 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
5360 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
7772 KB |
Output is correct |
| 2 |
Correct |
216 ms |
7224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
17264 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
551 ms |
18616 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
713 ms |
20844 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
834 ms |
20912 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1006 ms |
20200 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
