1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <vector>
#include <map>
#include <set>

int n, m;
std::vector<std::vector<std::pair<int, int>>> E;
std::vector<bool> vis;
//std::vector<bool> ignore;
//
//std::set<int> s1;
//std::set<std::pair<int, int>> s2;
//std::set<std::tuple<int, int, int>> s3;
//
//inline void update(std::pair<int, std::pair<int, int>>& p, int v) {
//    if (p.first == 0) p.second.first = v;
//    if (p.first == 1) p.second.second = v;
//    p.first++;
//}
//
//inline void update(std::pair<int, std::pair<int, int>>& p, std::pair<int, std::pair<int, int>> const& v) {
//    if (p.first == 0) {
//        p.second.first = v.second.first;
//        p.second.second = v.second.second;
//    }
//    if (p.first == 1) p.second.second = v.second.first;
//    p.first += v.first;
//}
//
//std::map<int, std::pair<int, std::pair<int, int>>> dfs(int i, int ep=-1) {
//    vis[i] = 1;
//    std::cerr<<ep<<" ";
//
//    std::map<int, std::pair<int, std::pair<int, int>>> ret;
//    for (auto [x, ei] : E[i]) {
//        if (ignore[x]) continue;
//        if (ei != ep) {
//            if (vis[x]) {
//                if (x != i) update(ret[x], ei);
//            } else {
//                auto m = dfs(x, ei);
//                for (auto [k, v] : m) {
//                    if (k != i) update(ret[k], v);
//                }
//            }
//        }
//    }
//
//    ignore[i] = 1;
//
//    if (ep == -1) return ret;
//
//    if (ret.size() == 0) s1.insert(ep);
//    if (ret.size() == 1) {
//        if (ret.begin()->second.first == 1) s2.insert({ep, ret.begin()->second.second.first});
//        if (ret.begin()->second.first == 2) s3.insert({ep, ret.begin()->second.second.first, ret.begin()->second.second.second});
//    }
//    if (ret.size() == 2) {
//        if (ret.begin()->second.first == 1 && ret.rbegin()->second.first == 1) {
//            s3.insert({ep, ret.begin()->second.second.first, ret.rbegin()->second.second.first});
//        }
//    }
//
//    return ret;
//}

template<typename T>
inline bool cont(std::set<T> const& a, T const& b) {
    return a.find(b) != a.end();
}

int check(int i, int a, int b, int c) {
    if (vis[i]) return 0;
    int ret = 1;
    vis[i] = 1;
    for (auto [x, ei] : E[i]) {
        if (ei != a && ei != b && ei != c) ret += check(x, a, b, c);
    }
    return ret;
}

int main() {
    std::ios::sync_with_stdio(false);

    std::cin >> n >> m;
    E.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        --a; --b;
        E[a].push_back({b, i});
        E[b].push_back({a, i});
    }

    //vis.resize(n);
    //ignore.resize(n);
    //dfs(0);

    //for (int i = 0; i < n; ++i) {
    //    if (E[i].size() == 2) s2.insert({E[i][0].second, E[i][1].second});
    //    if (E[i].size() == 3) s3.insert({E[i][0].second, E[i][1].second, E[i][2].second});
    //}

    //std::cerr << "s1: "; for (auto x : s1) std::cerr << "(" << x << ") "; std::cerr << std::endl;
    //std::cerr << "s2: "; for (auto x : s2) std::cerr << "(" << x.first << "," <<x.second << ") "; std::cerr << std::endl;
    //std::cerr << "s3: "; for (auto x : s3) std::cerr << "(" << std::get<0>(x) << "," << std::get<1>(x) << "," << std::get<2>(x) << ") "; std::cerr << std::endl;

    long long ret = 0;
    for (int a = 0; a < m; ++a) {
        for (int b = a + 1; b < m; ++b) {
            for (int c = b + 1; c < m; ++c) {
                //bool x = true;
                //if (cont(s1, a) || cont(s1, b) || cont(s1, c) ||
                //        cont(s2, {a, b}) || cont(s2, {a, c}) || cont(s2, {b, a}) || cont(s2, {b, c}) || cont(s2, {c, a}) || cont(s2, {c, b}) ||
                //        cont(s3, {a, b, c}) || cont(s3, {a, c, b}) || cont(s3, {b, a, c}) || cont(s3, {b, c, a}) || cont(s3, {c, a, b}) || cont(s3, {c, b, a})) {
                //    ret++;
                //    x = false;
                //}
                vis = std::vector<bool>(m);
                int z = check(0, a, b, c);
                ret += z != n;
                //if (x != (z == n)) {
                //    std::cerr << "err " << z <<","<<x<< " -> " << a << " " << b << " " << c << std::endl;
                //}
            }
        }
    }

    std::cout << ret;

    return 0;
}