#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define F first
#define S second
#define rand rnd

using namespace std;

mt19937 rnd;

ll solve(int n, int p, vector <pair<int, int>> vvod) {
    ll inf = 1e18;
    int mod = 1e9 + 7;
    set <pair <int,int>> st;
    map <pair <int,int>, int> mp;
    vector <int> cnt(n);
    for (int i = 0; i < n; i++) {
        int x = vvod[i].F;
        int y = vvod[i].S;
        cnt[x]++;
        cnt[y]++;
        if (x > y) swap(x, y);
        st.insert({x, y});
        mp[ {x, y}]++;
    }
    int extra = 0;
    for (auto x : st) {
        if (cnt[x.F] + cnt[x.S] - mp[ {x.F, x.S}] >= p) continue;
        if (cnt[x.F] + cnt[x.S] >= p) extra++;
    }
    ll ans = 0;
    sort(cnt.rbegin(),cnt.rend());
    for (int i = 0; i < n; i++) {
        if (cnt[i] < p / 2) break;
        int l = i + 1, r = n - 1, j = 0;
        while (l <= r) {
            int mid = (l + r)/2;
            if (cnt[mid] + cnt[i] >= p) {
                l = mid + 1;
                j = mid;
            } else r = mid - 1;
        }
        j = min(j, n - 1);
        ans += max(0, j - i);
    }
    return ans - extra;
}

ll wa6(int n, int p, vector <pair<int, int>> vvod) {
    ll inf = 1e18;
    int mod = 1e9 + 7;
    set <pair <int,int>> st;
    map <pair <int,int>, int> mp;
    vector <int> cnt(n);
    for (int i = 0; i < n; i++) {
        int x = vvod[i].F;
        int y = vvod[i].S;
        cnt[x]++;
        cnt[y]++;
        if (x > y) swap(x, y);
        st.insert({x, y});
        mp[ {x, y}]++;
    }
    ll ans = 0;
    sort(cnt.rbegin(),cnt.rend());
    for (int i = 0; i < n; i++) {
        if (cnt[i] < p / 2) break;
        int l = i + 1, r = n - 1, j = 0;
        while (l <= r) {
            int mid = (l + r)/2;
            if (cnt[mid] + cnt[i] >= p) {
                l = mid + 1;
                j = mid;
            } else r = mid - 1;
        }
        j = min(j, n - 1);
        ans += max(0, j - i);
    }
    return ans;
}

ll wa13(int n, int p, vector <pair<int, int>> vvod) {
    ll inf = 1e18;
    int mod = 1e9 + 7;
    set <pair <int,int>> st;
    map <pair <int,int>, int> mp;
    vector <int> cnt(n);
    for (int i = 0; i < n; i++) {
        int x = vvod[i].F;
        int y = vvod[i].S;
        cnt[x]++;
        cnt[y]++;
        st.insert({x, y});
        mp[{x, y}]++;
    }
    int extra = 0;
    for (auto x : st) {
        if (cnt[x.F] + cnt[x.S] - mp[ {x.F, x.S}] >= p) continue;
        if (cnt[x.F] + cnt[x.S] >= p) extra++;
    }
    ll ans = 0;
    sort(cnt.rbegin(),cnt.rend());
    for (int i = 0; i < n; i++) {
        if (cnt[i] < p / 2) break;
        int l = i + 1, r = n - 1, j = 0;
        while (l <= r) {
            int mid = (l + r)/2;
            if (cnt[mid] + cnt[i] >= p) {
                l = mid + 1;
                j = mid;
            } else r = mid - 1;
        }
        j = min(j, n - 1);
        ans += max(0, j - i);
    }
    return ans - extra;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif //LOCAL
    ll cnt = 0;
    rnd.seed(time(0));
    int N = 3e5;
    while (true) {
        int n = rnd() % (N - 100000) + 100000;
        int k = rnd() % 15;
        int kek = rnd() % 500 + 19500;
        vector <pair<int, int>> v(n, {-1, -1});
        for (int i = 0; i < n; i++) {
            int x = rnd() % kek;
            while (x == i) x = rand() % kek;
            int y = rnd() % kek;
            while (y == i || y == x) y = rand() % kek;
            v[i].F = x;
            v[i].S = y;
            if (rnd() % 3) swap(v[i].F, v[i].S);
        }
        ll ok = solve(n, k, v);
        ll wa1 = wa6(n, k, v);
        ll wa2 = wa13(n, k, v);
        if (ok != wa2) {
            cout << n << ' ' << k << endl;
            for (int i = 0; i < n; i++) {
                cout << v[i].F + 1 << ' ' << v[i].S + 1 << endl;
            }
            cout << kek << endl;
            return 0;
        }
        if (cnt % 100 == 0) {
            cerr << n << ' ' << k << ' ' << kek << ' ' << cnt << endl;
        }
        cnt++;
    }
}