Берляндия — туристическая страна! Во всяком случае, она такой может стать — уверено правительство Берляндии.

Берляндия состоит из n городов, некоторые пары которых соединены двусторонними дорогами. Каждая дорога соединяет два различных города. В Берляндии нет дорог, соединяющих одинаковую пару городов. Из любого города можно добраться до любого другого по заданным двусторонним дорогам.

В соответствии с новой реформой каждая дорога будет превращена в одностороннюю — ориентирована в одну из двух сторон.

Чтобы максимизировать туристическую привлекательность Берляндии для каждого города i после реформы будет подсчитана величина ri — количество таких городов x, что из города i существует ориентированный путь до города x. Иными словами, ri равно количеству городов, в которые можно добраться из города i, следуя по дорогам.

Правительство уверено, что внимание туристов будет сконцентрировано на минимальном из ri.

Помогите правительству Берляндии провести реформу так, чтобы максимизировать минимальное из ri.

Входные данные
Первая строка содержит два целых числа n, m (2 ≤ n ≤ 400 000, 1 ≤ m ≤ 400 000) — количество городов и количество дорог соответственно.

Далее следуют m строк, описывающие дороги в Берляндии: j-я из них содержит два целых числа uj и vj (1 ≤ uj, vj ≤ n, uj ≠ vj), где uj и vj — номера городов, которые соединены j-й дорогой.

Считайте, что города пронумерованы от 1 до n. Гарантируется, что из любого города можно добраться до любого другого по заданным двусторонним дорогам. В Берляндии нет дорог, соединяющих одинаковую пару городов.

Выходные данные
Первая строка должна содержать одно целое число — максимальное возможное значение min1 ≤ i ≤ n{ri} после ориентации всех дорог.

Следующие m строк должны содержать описание дорог после ориентации: j-я из них должна содержать два целых числа uj, vj, означающих, что j-я дорога ведет из города uj в город vj. Дороги следует выводить в том же порядке, в котором они заданы во входных данных.
что не так?
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define int ll

void solve(){
int n, m;
cin >> n >> m;
vector<pair<int, int> >edges;
vector<vector<int> >g(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
edges.push_back({u, v});
g[u].push_back(i);
g[v].push_back(i);
}
vector<int>used(n + 1), depth(n + 1), min_depth(n + 1);
set<pair<int, int> > bad;
function<void(int, int)> dfs = [&](int u, int p) {
used[u] = 1; min_depth[u] = depth[u];
for (int id : g[u]) {
if (id != p) {
int v = (edges[id].first ^ edges[id].second ^ u);
edges[id] = {u, v};
if (used[v]) {
min_depth[u] = min(min_depth[u], depth[v]);
} else {
depth[v] = depth[u] + 1;
dfs(v, id);
if (min_depth[v] > depth[u]) {
bad.insert({min(u, v), max(u, v)});
}
min_depth[u] = min(min_depth[u], min_depth[v]);
}
}
}
};
for (int i = 1; i <= n; i++) {
if (!used[i]) {
dfs(i, i);
}
}
for (int i = 1; i <= n; i++) {
used[i] = 0;
}
vector<int>col(n + 1), kol(n + 1); int cnt = 0;
function<void(int)> dfs1 = [&](int u) {
used[u] = 1; col[u] = cnt; kol[cnt]++;
for (int id : g[u]) {
int v = (edges[id].first ^ edges[id].second ^ u);
if (bad.find({min(u, v), max(v, v)}) == bad.end() && !used[v]) {
dfs1(v);
}
}
};
for (int i = 1; i <= n; i++) {
if (!used[i]) {
dfs1(i); cnt++;
}
}
vector<vector<int> >G(cnt);
for (int i = 1; i <= n; i++) {
for (int id : g[i]) {
G[col[i]].push_back(id);
}
}
int max_col = max_element(kol.begin(), kol.end()) - kol.begin();
queue<int>q;
vector<int>usd(m);
while (q.size()) {
int U = q.front(); q.pop();
for (int id : G[U]) {
if (usd[id]) {
continue;
}
if (U == col[edges[id].first]) {
swap(edges[id].first, edges[id].second);
}
q.push(edges[id].second);
usd[id] = 1;
}
}
cout << kol[max_col] << '\n';
for (int i = 0; i < m; i++) {
cout << edges[i].first << ' ' << edges[i].second << '\n';
}
}

int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
srand(time(0));

text
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

// freopen("bridges.in", "r", stdin);
// freopen("bridges.out", "w", stdout);
#endif

int tests = 1;

// cin >> tests;
while (tests--) {
solve();
}

text
#ifdef DEBUG
    cout << '\n' << 1.0 * clock() / CLOCKS_PER_SEC;
#endif

return 0;

}
вот тест который не работает
12 16
12 3
10 12
12 9
4 10
1 12
10 6
2 4
7 10
3 8
9 8
10 5
1 11
2 11
11 10
12 2
3 10