Настройки поиска

import java.io.*;
import java.util.*;
import java.math.*;

public class islands_aa {

    public static void main(String[] args) throws Throwable {
        new islands_aa().run();
    }

    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;
    boolean eof = false;
    Random rand = new Random(this.hashCode());

    private void run() throws Throwable {
        Locale.setDefault(Locale.US);
        br = new BufferedReader(new FileReader(FNAME + ".in"));
        out = new PrintWriter(FNAME + ".out");
        solve();
        out.close();
    }

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return "0";
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(nextToken());
    }

    void myAssert(boolean u, String message) {
        if (!u) {
            throw new Error("Assertion failed!!! " + message);
        }
    }

    int inBounds(int x, int l, int r, String name) {
        myAssert(l <= x && x <= r, name + " not in bounds: " + x + " not in ["
                + l + ".." + r + "]");
        return x;
    }

    String FNAME = "islands";

    ArrayList<Integer>[] g;
    int[] c;

    private void solve() throws IOException {
        int n = inBounds(nextInt(), 1, 100000, "n");
        int m = inBounds(nextInt(), 0, n, "m");
        g = new ArrayList[n];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<Integer>();
        }
        while (m-- > 0) {
            int x = inBounds(nextInt(), 1, n, "x") - 1;
            int y = inBounds(nextInt(), 1, n, "y") - 1;
            myAssert(x != y, "x(" + x + ") == y(" + y + "!!!");
            g[x].add(y);
            g[y].add(x);
        }
        for (int i = 0; i < g.length; i++) {
            inBounds(g[i].size(), 0, 2, "deg(" + (i + 1) + ")");
        }
        c = new int[n];
        Arrays.fill(c, -1);
        int k = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] < 0) {
                dfs(i, k++);
            }
        }
        long[] v = new long[k];
        long[] e = new long[k];
        for (int i = 0; i < c.length; i++) {
            v[c[i]]++;
            e[c[i]] += g[i].size();
        }
        for (int i = 0; i < e.length; i++) {
            e[i] /= 2;
        }
        long ans = 0;
        for (int i = 0; i < v.length; i++) {
            if (v[i] == e[i]) { // cycle
                long q = (v[i] + 1) / 2;
                ans += v[i] * q * (q - (v[i] % 2));
            } else { // chain
                ans += v[i] * (v[i] + 1) * (2 * v[i] + 1) / 6 - v[i]
                        * (v[i] + 1) / 2;
            }
        }
        out.println(ans);
    }

    private void dfs(int x, int k) {
        c[x] = k;
        for (int i : g[x]) {
            if (c[i] < 0) {
                dfs(i, k);
            }
        }
    }

}