Загрузка данных


#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

struct Edge {
    int to;
    int id;
};

int n, m;
vector<vector<Edge>> adj;
vector<int> tin, low;
vector<bool> is_bridge;
int timer = 0;

//алгоритм Тарьяна
void find_bridges(int v, int p_edge = -1) {
    tin[v] = low[v] = ++timer;
    for (auto& edge : adj[v]) {
        if (edge.id == p_edge) continue;
        int to = edge.to;
        if (tin[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            find_bridges(to, edge.id);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v]) {
                is_bridge[edge.id] = true;
            }
        }
    }
}

vector<int> comp_id;
int comp_count = 0;

void comp(int v, int cid) {
    comp_id[v] = cid;
    for (auto& edge : adj[v]) {
        if (is_bridge[edge.id]) continue;
        int to = edge.to;
        if (comp_id[to] == -1) {
            comp(to, cid);
        }
    }
}

vector<vector<int>> tree_adj;
vector<int> comp_size;
vector<bool> visited;
long long total_critical_sum = 0;

int tr(int v, int p = -1) {
    visited[v] = true;
    int sz = comp_size[v];
    for (int to : tree_adj[v]) {
        if (to == p) continue;
        int sub_sz = tr(to, v);
        total_critical_sum += (long long)sub_sz * (n - sub_sz);
        sz += sub_sz;
    }
    return sz;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;

    adj.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin>>u>>v;
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }

    tin.assign(n+1, 0);
    low.assign(n+1, 0);
    is_bridge.assign(m, false);

    for (int i = 1; i <= n; i++) {
        if (!tin[i]) {
            find_bridges(i);
        }
    }

    comp_id.assign(n+1, -1);
    for (int i = 1; i <= n; i++) {
        if (comp_id[i] == -1) {
            comp_count++;
            comp(i, comp_count);
        }
    }

    //дерево компонент
    comp_size.assign(comp_count+1, 0);
    for (int i = 1; i <= n; i++) {
        comp_size[comp_id[i]]++;
    }

    tree_adj.resize(comp_count + 1);
    for (int u = 1; u <= n; ++u) {
        for (auto& edge : adj[u]) {
            int v = edge.to;
            if (is_bridge[edge.id]) {
                int cu = comp_id[u];
                int cv = comp_id[v];
                if (cu != cv) {
                    tree_adj[cu].push_back(cv);
                }
            }
        }
    }

    visited.assign(comp_count + 1, false);
    for (int i = 1; i <= comp_count; ++i) {
        if (!visited[i]) {
            tr(i);
        }
    }

    long long total_pairs = (long long)n*(n-1)/2;

    long long g = gcd(total_critical_sum, total_pairs);
    
    cout << total_critical_sum / g <<"/"<< total_pairs / g << endl;

    return 0;
}