#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class BinaryIndexedTree { private: int n; vector data; public: BinaryIndexedTree(int n){ // コンストラクタ this->n = n; data.assign(n+1, 0); } void add(int k, int x){ // k番目の要素にxを加算する ++ k; while(k <= n){ data[k] += x; k += k & -k; } } int sum(int k){ // 区間[0,k]の総和を返す ++ k; int ret = 0; while(k > 0){ ret += data[k]; k -= k & -k; } return ret; } int sum(int a, int b){ // 区間[a,b]の総和を返す return sum(b) - sum(a-1); } int upper_bound(int x){ // 総和が初めてxを超える位置を返す(ただし、各位置の数値が非負数であることを前提とする) int b = 1; while(b < n) b *= 2; int a = 0; while(b > 0){ if(a+b <= n && x >= data[a+b]){ x -= data[a+b]; a += b; } b /= 2; } return (a < n)? a : -1; } int lower_bound(int x){ // 総和が初めてx以上になる位置を返す(ただし、各位置の数値が非負数であることを前提とする) return upper_bound(x-1); } }; int main() { int n, m; cin >> n >> m; vector a(n), b(n); vector v(m, -1); for(int i=0; i> a[i] >> b[i]; v[a[i]] = v[b[i]] = i; if(a[i] > b[i]) swap(a[i], b[i]); } BinaryIndexedTree bit(m); int cnt = 0; long long ans = 0; for(int i=0; i