DFS Tree

Cây DFS và giá trị low

Chạy DFS, gán $tin_u$ khi vào $u$. Định nghĩa $low_u$ là $tin$ nhỏ nhất chạm tới được từ cây con của $u$ bằng cách đi xuống theo cạnh cây rồi dùng tối đa một cạnh ngược. Tính khi DFS lùi về: $low_u = \min(tin_u,\ tin_w \text{ với mọi cạnh ngược } u \text{-} w,\ low_v \text{ với mọi con } v)$.

Cạnh cây $(u, v)$ (với $v$ là con) là cầu khi và chỉ khi $low_v > tin_u$: cây con của $v$ không có cạnh ngược nào lên tới $u$ hay cao hơn, nên bỏ cạnh $(u, v)$ thì cây con đó tách ra. Cạnh ngược không bao giờ là cầu vì nó nằm trên một chu trình. Khi đi xuống, bỏ qua đúng cạnh vừa đi tới (theo chỉ số cạnh, không theo đỉnh cha), để cạnh song song tới cha vẫn được tính là cạnh ngược.

void dfs(ll u, ll pe) {
    tin[u] = low[u] = ++timer;
    for (pair<ll, ll> e : g[u]) {
        ll v = e.first, id = e.second;
        if (id == pe) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) isb[id] = 1;
        }
    }
}

Ví dụNhững Tuyến Đường Không Thể Thiếu

Đề. Đồ thị vô hướng đơn liên thông $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh. In mọi cầu, đầu nhỏ trước, sắp theo thứ tự từ điển.

Lời giải. DFS tính tin và low như trên. Cạnh cây $(u, v)$ là cầu khi low[v] > tin[u]: không cạnh ngược nào từ cây con của $v$ chạm tới $u$ hay cao hơn, nên bỏ cạnh đó thì cây con tách ra.

Bước 1: DFS theo chỉ số cạnh. pe là chỉ số cạnh vừa đi xuống $u$; bỏ qua đúng cạnh đó, mọi cạnh tới đỉnh đã thăm khác là cạnh ngược và cập nhật low[u] bằng tin[v]. Sau khi gọi xong con $v$, low[u] nhận low[v]: cạnh ngược từ cây con của $v$ cũng là đường vòng của $u$.

void dfs(ll u, ll pe) {
    tin[u] = low[u] = ++timer;
    for (pair<ll, ll> e : g[u]) {
        ll v = e.first, id = e.second;
        if (id == pe) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) isb[id] = 1;
        }
    }
}

Bước 2: gom và sắp. Đưa đầu nhỏ lên trước rồi sắp theo cặp để in đúng thứ tự đề đòi.

for (ll i = 1; i <= m; i++)
    if (isb[i]) res.push_back({min(eu[i], ev[i]), max(eu[i], ev[i])});
sort(res.begin(), res.end());

Đệ quy sâu tới $10^5$ tầng; thường vẫn chạy được với ngăn xếp mặc định của trình chấm, nhưng đồ thị lớn hơn thì nên viết bằng ngăn xếp tường minh như bài 76.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, M = 2e5 + 5;
ll n, m, timer, tin[N], low[N], eu[M], ev[M], isb[M];
vector<pair<ll, ll>> g[N];

void dfs(ll u, ll pe) {
    tin[u] = low[u] = ++timer;
    for (pair<ll, ll> e : g[u]) {
        ll v = e.first, id = e.second;
        if (id == pe) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) isb[id] = 1;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        g[eu[i]].push_back({ev[i], i});
        g[ev[i]].push_back({eu[i], i});
    }
    dfs(1, 0);
    vector<pair<ll, ll>> res;
    for (ll i = 1; i <= m; i++)
        if (isb[i]) res.push_back({min(eu[i], ev[i]), max(eu[i], ev[i])});
    sort(res.begin(), res.end());
    cout << res.size() << '\n';
    for (pair<ll, ll> p : res) cout << p.first << ' ' << p.second << '\n';
}

Input6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

Output1
3 4

$O(n + m)$ cộng phần sắp kết quả.

Khớp

Đỉnh $u$ không phải gốc là khớp khi và chỉ khi nó có một con $v$ với $low_v \ge tin_u$: cây con của $v$ không có cạnh ngược nào vượt lên trên $u$, nên bỏ $u$ thì cây con đó tách khỏi phần phía trên. Lần này dấu bằng được phép, vì cạnh ngược về chính $u$ cũng mất khi bỏ $u$.

Gốc không có phía trên, nên cần quy tắc riêng: gốc là khớp khi và chỉ khi nó có ít nhất hai con trong cây DFS. Các cây con của gốc không nối với nhau bằng cạnh ngang (DFS không có cạnh ngang), nên bỏ gốc thì chúng tách rời. Với đồ thị nhiều thành phần, gọi DFS từ mọi đỉnh chưa thăm, mỗi lần là một gốc mới.

Ví dụNhững Thành Phố Trọng Yếu

Đề. Đồ thị vô hướng đơn liên thông $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh. In số khớp và các khớp tăng dần.

Lời giải. Hai quy tắc khớp như trên. Đỉnh không phải gốc là khớp khi có con $v$ với low[v] >= tin[u]: dấu bằng được phép vì cạnh ngược chạm đúng $u$ cũng mất khi bỏ $u$. Gốc là khớp khi có từ hai con trở lên trong cây DFS. Đồ thị đơn nên bỏ qua đỉnh cha là đủ; có cạnh song song thì phải bỏ theo chỉ số cạnh như ví dụ trước.

Bước 1: DFS có đếm con. child đếm số con trong cây DFS, chỉ dùng cho gốc; kiểm quy tắc gốc sau khi duyệt hết hàng xóm.

void dfs(ll u, ll p) {
    tin[u] = low[u] = ++timer;
    ll child = 0;
    for (ll v : g[u]) {
        if (v == p) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            child++;
            if (p && low[v] >= tin[u]) cut[u] = 1;
        }
    }
    if (!p && child >= 2) cut[u] = 1;
}

Bước 2: in các khớp tăng dần. Duyệt $u = 1..n$ thì tự tăng dần.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5;
ll n, m, timer, tin[N], low[N], cut[N];
vector<ll> g[N];

void dfs(ll u, ll p) {
    tin[u] = low[u] = ++timer;
    ll child = 0;
    for (ll v : g[u]) {
        if (v == p) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            child++;
            if (p && low[v] >= tin[u]) cut[u] = 1;
        }
    }
    if (!p && child >= 2) cut[u] = 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    vector<ll> res;
    for (ll u = 1; u <= n; u++)
        if (cut[u]) res.push_back(u);
    cout << res.size() << '\n';
    for (ll u : res) cout << u << ' ';
    cout << '\n';
}

Input6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

Output2
3 4

$O(n + m)$.

Ví dụMắt Xích Gãy

Đề. Đồ thị vô hướng đơn $n \le 10^4$ đỉnh, có thể nhiều thành phần. In số khớp và số cầu.

Lời giải. Một hàm DFS làm cả hai việc, gọi từ mọi đỉnh chưa thăm vì đồ thị có thể nhiều thành phần. Mỗi lần gọi là một gốc mới với p = 0, nên quy tắc gốc áp dụng riêng cho từng thành phần.

Bước 1: hai điều kiện trong cùng một vòng. >= cho khớp, > cho cầu. Đây là chỗ hay nhầm: cạnh ngược về đúng $u$ làm $(u, v)$ không phải cầu, nhưng không cứu được $u$ khỏi là khớp.

dfs(v, u);
low[u] = min(low[u], low[v]);
child++;
if (p && low[v] >= tin[u]) cut[u] = 1;
if (low[v] > tin[u]) bridges++;

Bước 2: mọi thành phần.

for (ll u = 1; u <= n; u++)
    if (!tin[u]) dfs(u, 0);

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e4 + 5;
ll n, m, timer, tin[N], low[N], cut[N], bridges;
vector<ll> g[N];

void dfs(ll u, ll p) {
    tin[u] = low[u] = ++timer;
    ll child = 0;
    for (ll v : g[u]) {
        if (v == p) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            child++;
            if (p && low[v] >= tin[u]) cut[u] = 1;
            if (low[v] > tin[u]) bridges++;
        }
    }
    if (!p && child >= 2) cut[u] = 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (ll u = 1; u <= n; u++)
        if (!tin[u]) dfs(u, 0);
    ll cuts = 0;
    for (ll u = 1; u <= n; u++) cuts += cut[u];
    cout << cuts << ' ' << bridges << '\n';
}

Input5 4
1 2
2 3
3 1
4 5

Output0 1

$O(n + m)$.

Thành phần liên thông mạnh

Trên đồ thị có hướng, hai đỉnh liên thông mạnh khi mỗi đỉnh đi tới được đỉnh kia. Quan hệ này chia đỉnh thành các thành phần liên thông mạnh (strongly connected component, SCC). Thuật toán Kosaraju dùng hai lần DFS:

1. DFS trên đồ thị gốc, ghi các đỉnh theo thứ tự xong (đã duyệt hết các đỉnh đi ra).
2. DFS trên đồ thị ngược, lấy đỉnh theo thứ tự xong giảm dần; mỗi lần gọi từ ngoài thu được đúng một SCC.

Đỉnh xong muộn nhất thuộc một SCC “nguồn” của đồ thị nén. Trên đồ thị ngược, từ nó chỉ tới được các đỉnh trong chính SCC đó, vì các cung vào SCC nguồn trong đồ thị gốc không tồn tại. Lấy SCC đó ra rồi lặp lại với phần còn lại. Tổng $O(n + m)$. Thuật toán Tarjan làm trong một lần DFS bằng ngăn xếp và $low$, cho các SCC theo thứ tự tô pô ngược; Kosaraju cho chúng theo thứ tự tô pô xuôi.

Ví dụPhân Vùng Tương Hỗ

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cung. In số SCC và nhãn SCC của từng đỉnh.

Lời giải. Kosaraju, hai lần DFS. Lần một trên đồ thị gốc ghi thứ tự xong. Lần hai duyệt theo thứ tự xong giảm dần trên đồ thị ngược: mỗi đỉnh chưa có nhãn mở một SCC mới, và DFS trên đồ thị ngược từ nó chỉ lan được trong đúng SCC đó, vì các SCC tới được từ nó trên đồ thị ngược đều đã có nhãn từ trước.

Bước 1: đồ thị gốc và đồ thị ngược. Dựng cùng lúc khi đọc cung.

g[u].push_back(v);
rg[v].push_back(u);

Bước 2: thứ tự xong. dfs1 đẩy $u$ vào ord khi đã duyệt xong mọi đỉnh đi ra từ nó; gọi từ mọi đỉnh chưa thăm.

void dfs1(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs1(v);
    ord.push_back(u);
}

Bước 3: gán nhãn trên đồ thị ngược. comp dùng 0 làm “chưa có nhãn”, nên nhãn bắt đầu từ 1.

void dfs2(ll u) {
    comp[u] = k;
    for (ll v : rg[u])
        if (!comp[v]) dfs2(v);
}

for (ll i = n - 1; i >= 0; i--)
    if (!comp[ord[i]]) {
        k++;
        dfs2(ord[i]);
    }

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5;
ll n, m, k, vis[N], comp[N];
vector<ll> g[N], rg[N], ord;

void dfs1(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs1(v);
    ord.push_back(u);
}

void dfs2(ll u) {
    comp[u] = k;
    for (ll v : rg[u])
        if (!comp[v]) dfs2(v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    for (ll u = 1; u <= n; u++)
        if (!vis[u]) dfs1(u);
    for (ll i = n - 1; i >= 0; i--)
        if (!comp[ord[i]]) {
            k++;
            dfs2(ord[i]);
        }
    cout << k << '\n';
    for (ll u = 1; u <= n; u++) cout << comp[u] << ' ';
    cout << '\n';
}

Input6 7
1 2
2 3
3 1
3 4
4 5
5 4
5 6

Output3
1 1 1 2 2 3

$O(n + m)$.

Đồ thị nén

Nén mỗi SCC thành một đỉnh và giữ các cung nối hai SCC khác nhau: được một DAG, vì một chu trình giữa các SCC sẽ gộp chúng thành một. Nhiều bài trên đồ thị có hướng tổng quát trở thành bài trên DAG: số đỉnh nguồn cần chọn để tới được mọi nơi là số SCC có bậc vào 0; đường thu nhiều giá trị nhất là đường dài nhất trên DAG với trọng số SCC bằng tổng các đỉnh trong đó. Nhãn của Kosaraju đã theo thứ tự tô pô, nên quy hoạch động chỉ cần duyệt nhãn theo thứ tự ngược.

Ví dụNguồn Phát Tối Thiểu

Đề. Mạng có hướng $n \le 800$ đỉnh, $m \le 2 \cdot 10^5$ cung. Chọn ít đỉnh nhất để thông tin từ chúng tới được mọi đỉnh.

Lời giải. Nén mỗi thành phần liên thông mạnh thành một đỉnh, được đồ thị không chu trình. Một SCC không có cung vào từ SCC khác thì không nhận được thông tin từ ngoài, nên phải chọn một đỉnh trong nó. Ngược lại, chọn một đỉnh trong mỗi SCC như vậy là đủ: mọi SCC khác đều tới được từ một SCC nguồn nào đó. Đáp án là số SCC nguồn.

Bước 1: Kosaraju như ví dụ trước.

Bước 2: đánh dấu SCC có cung vào. Duyệt mọi cung $u \to v$; hai đầu khác SCC thì SCC của $v$ có cung vào từ ngoài. Cung trong cùng một SCC không tính.

for (ll u = 1; u <= n; u++)
    for (ll v : g[u])
        if (comp[u] != comp[v]) hasIn[comp[v]] = 1;
ll ans = 0;
for (ll c = 1; c <= k; c++) ans += !hasIn[c];

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 805;
ll n, m, k, vis[N], comp[N], hasIn[N];
vector<ll> g[N], rg[N], ord;

void dfs1(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs1(v);
    ord.push_back(u);
}

void dfs2(ll u) {
    comp[u] = k;
    for (ll v : rg[u])
        if (!comp[v]) dfs2(v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    for (ll u = 1; u <= n; u++)
        if (!vis[u]) dfs1(u);
    for (ll i = n - 1; i >= 0; i--)
        if (!comp[ord[i]]) {
            k++;
            dfs2(ord[i]);
        }
    for (ll u = 1; u <= n; u++)
        for (ll v : g[u])
            if (comp[u] != comp[v]) hasIn[comp[v]] = 1;
    ll ans = 0;
    for (ll c = 1; c <= k; c++) ans += !hasIn[c];
    cout << ans << '\n';
}

Input6 7
1 2
2 1
3 4
4 3
2 5
4 5
5 6

Output2

$O(n + m)$.

Ví dụHành Trình Thu Thập

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh có giá trị dương, $m \le 2 \cdot 10^5$ cung. Đi từ đỉnh tùy ý theo các cung, mỗi đỉnh thu giá trị một lần. Tìm tổng lớn nhất.

Lời giải. Trong một SCC đi được hết mọi đỉnh rồi rời đi, nên mỗi SCC có giá trị bằng tổng các đỉnh của nó, và bài thành tìm đường có tổng lớn nhất trên đồ thị nén (không chu trình). Kosaraju gán nhãn theo thứ tự tô pô xuôi: mọi cung nén đi từ nhãn nhỏ sang nhãn lớn, nên quy hoạch động duyệt nhãn từ lớn về nhỏ.

Bước 1: Kosaraju như các ví dụ trước.

Bước 2: dựng đồ thị nén. val[c] là tổng giá trị các đỉnh của SCC $c$; dg[c] là các SCC kề sau $c$. Có thể có cung lặp, không sao vì chỉ lấy max.

for (ll u = 1; u <= n; u++) {
    val[comp[u]] += w[u];
    for (ll v : g[u])
        if (comp[u] != comp[v]) dg[comp[u]].push_back(comp[v]);
}

Bước 3: đường tổng lớn nhất. dp[c] là tổng lớn nhất của một đường bắt đầu ở SCC $c$; duyệt $c$ từ $k$ về 1 thì dp của các SCC kề sau đã xong. Đáp án là max mọi dp[c], vì được xuất phát ở đỉnh tùy ý.

for (ll c = k; c >= 1; c--) {
    dp[c] = 0;
    for (ll d : dg[c]) dp[c] = max(dp[c], dp[d]);
    dp[c] += val[c];
    ans = max(ans, dp[c]);
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5;
ll n, m, k, w[N], vis[N], comp[N], val[N], dp[N];
vector<ll> g[N], rg[N], dg[N], ord;

void dfs1(ll u) {
    vis[u] = 1;
    for (ll v : g[u])
        if (!vis[v]) dfs1(v);
    ord.push_back(u);
}

void dfs2(ll u) {
    comp[u] = k;
    for (ll v : rg[u])
        if (!comp[v]) dfs2(v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> w[i];
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    for (ll u = 1; u <= n; u++)
        if (!vis[u]) dfs1(u);
    for (ll i = n - 1; i >= 0; i--)
        if (!comp[ord[i]]) {
            k++;
            dfs2(ord[i]);
        }
    for (ll u = 1; u <= n; u++) {
        val[comp[u]] += w[u];
        for (ll v : g[u])
            if (comp[u] != comp[v]) dg[comp[u]].push_back(comp[v]);
    }
    ll ans = 0;
    for (ll c = k; c >= 1; c--) {
        dp[c] = 0;
        for (ll d : dg[c]) dp[c] = max(dp[c], dp[d]);
        dp[c] += val[c];
        ans = max(ans, dp[c]);
    }
    cout << ans << '\n';
}

Input6 7
4 2 7 3 5 1
1 2
2 3
3 1
3 4
4 5
5 4
5 6

Output22

$O(n + m)$.

Định hướng cạnh

Đồ thị vô hướng liên thông định hướng được thành đồ thị liên thông mạnh khi và chỉ khi nó không có cầu (định lý Robbins). Một cầu, theo hướng nào, cũng chỉ cho đi một chiều giữa hai phía. Ngược lại, khi không có cầu, định hướng theo DFS: cạnh cây từ cha xuống con, cạnh ngược từ con cháu lên tổ tiên. Từ gốc đi xuống được mọi đỉnh; từ mỗi đỉnh, cây con của nó luôn có một cạnh ngược vượt lên trên ($low_v < tin_v$ vì không có cầu), nên từng bước leo được về gốc.

Ví dụĐịnh Hướng Bền Vững

Đề. Đồ thị vô hướng đơn liên thông $n \le 10^5$ đỉnh, $m \le 3 \cdot 10^5$ cạnh. Định hướng mọi cạnh để được đồ thị liên thông mạnh, in hướng theo thứ tự cạnh; không được thì in 0.

Lời giải. Định lý Robbins: đồ thị vô hướng liên thông định hướng được thành liên thông mạnh khi và chỉ khi nó không có cầu. Cách định hướng lấy thẳng từ cây DFS: cạnh cây hướng từ cha xuống con, cạnh ngược hướng từ đỉnh dưới lên tổ tiên. Không có cầu thì từ gốc đi xuống được mọi đỉnh theo cạnh cây, và từ mỗi đỉnh leo về được gốc bằng các cạnh ngược, nên đồ thị liên thông mạnh.

Bước 1: định hướng lúc xét cạnh lần đầu. Mỗi cạnh xuất hiện ở hai danh sách kề; used[id] cho biết đã định hướng chưa, lần đầu xét thì ghi u → v với $u$ là đỉnh đang đứng. Lần đầu xét cạnh tới $v$ chưa thăm là cạnh cây, đúng hướng cha xuống con. Lần đầu xét cạnh tới $v$ đã thăm thì $v$ là tổ tiên còn trên ngăn xếp (nếu $v$ là con cháu đã xong thì cạnh đã được xét từ phía $v$), nên hướng đi lên tổ tiên.

if (!used[id]) {
    used[id] = 1;
    da[id] = u;
    db[id] = v;
}

Bước 2: tìm cầu trong cùng lượt DFS. Có cầu thì không định hướng được, in 0.

if (tin[v]) low[u] = min(low[u], tin[v]);
else {
    dfs(v, id);
    low[u] = min(low[u], low[v]);
    if (low[v] > tin[u]) bad = 1;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, M = 3e5 + 5;
ll n, m, timer, tin[N], low[N], da[M], db[M], used[M];
bool bad;
vector<pair<ll, ll>> g[N];

void dfs(ll u, ll pe) {
    tin[u] = low[u] = ++timer;
    for (pair<ll, ll> e : g[u]) {
        ll v = e.first, id = e.second;
        if (id == pe) continue;
        if (!used[id]) {
            used[id] = 1;
            da[id] = u;
            db[id] = v;
        }
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) bad = 1;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    dfs(1, 0);
    if (bad) {
        cout << 0 << '\n';
        return 0;
    }
    for (ll i = 1; i <= m; i++) cout << da[i] << ' ' << db[i] << '\n';
}

Input5 6
1 2
2 3
3 1
3 4
4 5
5 3

Output1 2
2 3
3 1
3 4
4 5
5 3

$O(n + m)$.