Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * author: compounding
- * created: 2024-11-16 18:33:28
- **/
- #include <bits/stdc++.h>
- using namespace std;
- mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
- #define NeedForSpeed \
- ios_base::sync_with_stdio(false); \
- cin.tie(NULL); \
- cout.tie(NULL);
- #define int long long
- #define all(x) (x).begin(), (x).end()
- typedef vector<int> vi;
- typedef vector<bool> vb;
- typedef vector<vi> vvi;
- typedef vector<pair<int, int>> vpi;
- #define f first
- #define s second
- #define yes cout << "YES" << endl
- #define no cout << "NO" << endl
- #define endl "\n"
- const int mod = 1000000007;
- int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
- void solve()
- {
- int n, d, l;
- cin >> n >> d >> l;
- // edge cases
- if (n <= l)
- {
- cout << -1 << endl;
- return;
- }
- vector<pair<int, int>> edges;
- // straight line
- for (int i = 1; i <= d; i++)
- {
- edges.push_back({i, i + 1});
- }
- int mid = (d + 2) / 2;
- // all leaves in mid
- int leaves_left = l - 2;
- int curnode = d + 2;
- // leaves lagate hain
- queue<pair<int, int>> q;
- for (; curnode <= n && (leaves_left > 0); curnode++)
- {
- edges.push_back({mid, curnode});
- leaves_left--;
- q.push({curnode, 1});
- }
- // step 2
- if (curnode > n && leaves_left > 0)
- {
- cout << -1 << endl;
- return;
- }
- if (leaves_left == 0)
- {
- for (auto edge : edges)
- {
- cout << edge.first << " " << edge.second << endl;
- }
- return;
- }
- else
- {
- // leaves fullfilled, but not n (total number of nodes)
- int buffer = mid - 1;
- while (!q.empty())
- {
- auto [node, dist] = q.front();
- q.pop();
- if (dist + 1 <= buffer)
- {
- edges.push_back({node, curnode});
- q.push({curnode, dist + 1});
- curnode++;
- }
- }
- // as all nodes have not been used
- if (curnode <= n)
- {
- cout << -1 << endl;
- return;
- }
- else
- {
- for (auto edge : edges)
- {
- cout << edge.first << " " << edge.second << endl;
- }
- // cout << "geeks";
- }
- }
- return;
- }
- signed main()
- {
- NeedForSpeed;
- int t = 1;
- cin >> t;
- while (t--)
- {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment