fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. #define int long long
  5. #define endl "\n"
  6. #define vec vector
  7. #define pb push_back
  8. #define INF INT_MAX
  9. #define se second
  10. #define fi first
  11. #define pii pair<int, int>
  12. #define pil pair<int, long long>
  13. #define pli pair<long long, int>
  14. #define pll pair<long long, long long>
  15. #define str string
  16.  
  17. using ll = long long;
  18. using ull = unsigned long long;
  19. using ui = unsigned int;
  20.  
  21. const int MOD = 1000000007;
  22.  
  23. #define all(x) x.begin(), x.end()
  24. #define rall(x) x.rbegin(), x.rend()
  25.  
  26. using namespace std;
  27.  
  28. void solve() {
  29.     int n;
  30.     ll k;
  31.     cin >> n >> k;
  32.     __int128 mx = (__int128)n * (n - 1) * (n - 2) / 6;
  33.     if (k > mx + 1) {
  34.         cout << "No\n";
  35.         return;
  36.     }
  37.     ll r = k;
  38.     vec<int> S;
  39.     for (int s = n - 1; s >= 2; --s) {
  40.         ll f = (ll)s * (s - 1) / 2;
  41.         if (f <= r) {
  42.             S.pb(s);
  43.             r -= f;
  44.         }
  45.     }
  46.     int l = S.size();
  47.     int L = l + 1;
  48.     vec<ll> leaves(L + 2, 0), suf(L + 3, 0);
  49.     if (l == 0) {
  50.         leaves[1] = n - 1;
  51.     } else {
  52.         int s1 = S[0];
  53.         leaves[1] = (n - 1) - s1;
  54.         for (int i = 2; i <= L; ++i) {
  55.             int si1 = S[i - 2];
  56.             suf[i] = si1 - (L - (i - 1));
  57.         }
  58.         suf[L + 1] = 0;
  59.         for (int i = 2; i <= L; ++i) {
  60.             leaves[i] = suf[i] - suf[i + 1];
  61.         }
  62.     }
  63.     cout << "Yes\n";
  64.     vec<pii> edges;
  65.     edges.reserve(n - 1);
  66.     for (int i = 2; i <= L; ++i)
  67.         edges.emplace_back(i - 1, i);
  68.     int cur = L + 1;
  69.     for (int i = 1; i <= L; ++i) {
  70.         for (int j = 0; j < leaves[i]; ++j) {
  71.             edges.emplace_back(i, cur++);
  72.         }
  73.     }
  74.     for (auto &e : edges)
  75.         cout << e.fi << " " << e.se << "\n";
  76. }
  77.  
  78. signed main() {
  79.     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  80.     int t; cin >> t;
  81.     for (int i = 0; i < t; i++)
  82.         solve();
  83. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
2 1
2 2
4 0
5 7
5 5
stdout
copy 
Yes
1 2
No
Yes
1 2
1 3
1 4
Yes
1 2
2 3
2 4
3 5
Yes
1 2
2 3
1 4
3 5
https://ideone.com/b9aQYK
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!