MỘT ĐƯỜNG ĐI

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1e6 + 5;
constexpr int mod = 123456789;

int n, m;
vector<pair<int, int>> adj[N]; // Trong danh sách kề, anh lưu hai giá trị là {đỉnh, chỉ số cạnh (thứ tự nhập vào của cạnh trong input)}

int low[N], num[N], l; // Phục vụ cho quá trình dfs tìm cầu

bitset<N> vis; // Mảng đánh dấu đã duyệt qua bởi dfs chưa
bitset<N * 5> Critical; // Mảng đánh dấu cạnh

void Read()
{
    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;

        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }
}


// Quá trình thực hiện thuật toán Tarjan
void dfs(int v, int p = -1)
// Tham số của hàm dfs gồm có 2 giá trị là v - đỉnh hiện tại và p-cạnh vừa đi qua để đến v
// Nhiều nơi (Hầu hết trên mạng) hướng dẫn code tarjan lưu p là cha của v nhưng cách làm này không đúng với đa đồ thị
// Trên thực tế, ta chỉ cần không đi lại cạnh vừa đi qua là được, đây chính là lí dó anh lưu lại chỉ số cạnh trong danh sách kề
{
    low[v] = num[v] = ++l;

    for (auto i : adj[v])
        if (i.second != p)
        // Nếu cạnh này không phải là cạnh vừa được duyệt qua
        {
            if (!num[i.first]) // Nếu đỉnh i.first chưa được duyệt qua
            {
                dfs(i.first, i.second);
                low[v] = min(low[v], low[i.first]);

                if (low[i.first] > num[v])
                // Theo VNOI Wiki, low[i.first] == num[i.first], nhưng hai điều kiện này là tương đương nhau
                    Critical[i.second] = 1;
            }
            else {
                low[v] = min(low[v], num[i.first]);
                // Các em cần chú ý đoạn này, vì là đa đồ thị nên rất có thể cạnh này nối đến một con cháu của nó
                // Trong bài toán tìm cầu khớp, điều này không ảnh hưởng nhiều; song trong nhiều bài toán khác có thêm điều kiện, ta cần chú ý về điều kiện này có làm ảnh hưởng đến thuật toán ta thiết kế hay không
            }
        }
}

// Liệt kê thành phần liên thông sử dụng BFS
ll BFS(int x)
{
    int cnt(0); // Duy trì số lượng đỉnh của thành phần liên thông
    ll sum(0); // Duy trì tổng chỉ số của thành phần liên thông

    queue<int> q;

    q.emplace(x);
    vis[x] = 1;

    while (!q.empty())
    {
        int c = q.front();
        q.pop();

        ++cnt;
        sum += c;

        for (auto i : adj[c])
            if (Critical[i.second] && !vis[i.first]) /// Anh chỉ đi qua cầu
            {
                q.emplace(i.first);
                vis[i.first] = 1;
            }
    }

    return sum * cnt; // Số đỉnh * Tổng chỉ số
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
        if (!num[i])
            dfs(i);

    ll ans(0);

    for (int i = 1; i <= n; ++i)
        if (!vis[i])
            (ans += BFS(i)) %= mod;

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}