f.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int INF = 1e9 + 1;
const int MAXN = 4e5 + 10;
int fup[MAXN], tin[MAXN], col[MAXN], cnt_col[MAXN];
bool was[MAXN], is_bridge[MAXN];
vector <pair <int, int> > g[MAXN], g1[MAXN];
int timer;
vector <pair <int, int> > ans(MAXN);
vector <pair <pair <int, int>, int > > vec;
map <pair <int, int>, bool > ma;
void dfs(int v, int pr = -1){
    was[v] = 1;
    tin[v] = ++timer;
    fup[v] = tin[v];

    for (auto [to, num] : g[v]){
        if (!was[to]){
            dfs(to, v);
            fup[v] = min(fup[v], fup[to]);

            if (fup[to] > tin[v]){
                is_bridge[num] = 1;/*
                g1[v].pb({to, num});
                g1[to].pb({v, num});
                */
                vec.pb({{v, to}, num});
            }
            ans[num] = {v, to};
            ma[{v, to}] = 1;

        }
        else if (to != pr){
            fup[v] = min(fup[v], tin[to]);
            if (ma.count(make_pair(v, to)) == 0 && ma.count(make_pair(to, v)) == 0){
                ans[num] = {v, to};
                ma[{v, to}] = 1;
            }
        }
    }
}

void dfs2(int v, int comp){
    was[v] = 1;
    col[v] = comp;
    cnt_col[comp]++;

    for (auto [to, num] : g[v]){
        if (!was[to] && is_bridge[num] == 0){
            dfs2(to, comp);
        }
    }
}

void dfs3(int v){
    was[v] = 1;
    for (auto [to, num] : g1[v]){
        if (!was[to]){
            dfs3(to);
            if (col[ans[num].f] != to)
                swap(ans[num].f, ans[num].s);
        }
    }
}

void solve(){

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        g[x].pb({y, i});
        g[y].pb({x, i});
    }

    dfs(1, -1);

    for (int i = 1; i <= n; i++){
        was[i] = 0;
    }
    int cnt = 0;
    int finish = 1;
    int maxx = -1;
    for (int i = 1; i <= n; i++){
        if (!was[i]){
            cnt++;
            dfs2(i, cnt);
            if (cnt_col[col[i]] > maxx){
                maxx = cnt_col[col[i]];
                finish = col[i];
            }
        }
    }

    for (int i = 0; i < vec.size(); i++){
        g1[col[vec[i].f.f]].pb({col[vec[i].f.s], vec[i].s});
        g1[col[vec[i].f.s]].pb({col[vec[i].f.f], vec[i].s});
    }

    for (int i = 1; i <= n; i++){
        was[i] = 0;
    }
    cout << maxx << "\n";
    dfs3(finish);

    for (int i = 1; i <= m; i++){
        cout << ans[i].f << ' ' << ans[i].s << "\n";
    }
}
int main() {
    IOS;
    int t = 1;
   // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}