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


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

using namespace std;

void dfs(int u, int p, int& timer, vector<vector<int>>& adj, vector<int>& tin, vector<int>& low, long long n, long long& total_sum, vector<int>& sz) {
    tin[u] = low[u] = ++timer;
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (tin[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            dfs(v, u, timer, adj, tin, low, n, total_sum, sz);
            low[u] = min(low[u], low[v]);
            sz[u] += sz[v];
            if (low[v] > tin[u]) {
                long long s1 = sz[v];
                long long s2 = n - sz[v];
                total_sum += s1 * s2;
            }
        }
    }
}

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    if (!(cin >> n >> m)) return 0;
    
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> tin(n + 1, 0);
    vector<int> low(n + 1, 0);
    vector<int> sz(n + 1, 0);
    int timer = 0;
    long long total_sum = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!tin[i]) {
            dfs(i, -1, timer, adj, tin, low, n, total_sum, sz);
        }
    }
    
    long long total_pairs = (long long)n * (n - 1) / 2;
    long long g = gcd(total_sum, total_pairs);
    
    if (g == 0) {
        cout << "0/1\n";
    } else {
        cout << total_sum / g << "/" << total_pairs / g << "\n";
    }
    
    return 0;
}