I wrote a slightly better time complexity code for problem E Build a Tree

If it wasn't for printing edges my code beats solution code in processing

I request anyone to check if my code gives correct output for entire input space

Approach : Find largest number where this condition hold true

(k >= (m* m) / 2 + 2 * (n — m))

construct largest k for whose m edges : as in b2 (function)method continue this process for k-m(m)/2 and soon until k>remaining_n(remaining_n)/2 logic is provided im below code to handle remaining_n my code might still need optimisation

import java.util.*;

public class Main { static void b1(int x, int y) { if (x != 1) { System.out.println("1 " + x); } for (int i = x + 1; i <= y; i++) { System.out.println((i — 1) + " " + i); } }

static void b2(int x, int y) {
    if (x != 1) {
        System.out.println(1 + " " + x);
        if (y >= x + 1) {
            System.out.println("1 " + (x + 1));
        }
    } else {
        System.out.println("1 " + (x + 1));
    }
    for (int i = x + 2; i <= y; i++) {
        System.out.println((i - 2) + " " + i);
    }
}

static int b3(int n, int k) {
    int l = 2;
    int r = n;
    int res = -1;

    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (k >= (mid * mid) / 2 + 2 * (n - mid)) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return res;
}

static int b4(int n, int k) {
    int l = 1;
    int r = n;
    int res = -1;

    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (k >= (mid * mid) / 2 + 2 * (n - mid + 1)) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return (res - 1);
}

static void b7(int abc, int ab, int n, int k) {
    int abcd = -1;
    boolean flag = false;
    if (abc % 2 == 0) {
        abc--;
    }
    while (n > 0 && 2 * (n - 1) + abc + 1 <= k) {
        if (flag) {
            System.out.println(abc + " " + ab);
            flag = false;
            abcd = abc;
        } else {
            System.out.println(abc - 1 + " " + ab);
            flag = true;
            abcd = abc - 1;
        }
        n--;
        ab++;
        k = k - abc + 1;
    }
    while (n > 1) {
        System.out.println(1 + " " + ab);
        n--;
        ab++;
        k -= 2;
    }
    if (n == 1) {
        if(k==2){
            System.out.println(1 + " " + ab);
            return;
        }
        if (abcd == -1 || abcd % 2 == 0) {
            System.out.println(k - 1 + " " + ab);
        } else {
            System.out.println(k - 2 + " " + ab);
        }
    }

}

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int t = sc.nextInt();

    while (t-- > 0) {
        int ab = 1;
        int n = sc.nextInt();
        int m = n;
        int k = sc.nextInt();
        if (k % 2 == 1 || k < 2 * (n - 1) || k > (n * n) / 2) {
            System.out.println("-1");
        } else if (k == 2 * (n - 1)) {
            b1(1, n);
        } else if (k == n * n / 2) {
            b2(1, n);
        } else {
            int res = b3(n, k);
            int abc = res;
            n -= res;
            b2(ab, ab + res - 1);
            ab += res;
            k -= (res * res) / 2;

            if (n == 1) {
                if (k == 2) {
                    System.out.println(1 + " " + m);
                    continue;
                }

                if ((m - 1) % 2 == 0) {
                    System.out.println(k - 1 + " " + m);
                } else {
                    System.out.println(k - 2 + " " + m);
                }
                continue;
            }

            while (k > 0) {

                if (2 * n == k) {
                    for (int i = ab; i <= m; i++) {
                        System.out.println("1 " + i);
                    }
                    break;
                }
                if (k > (n * n) / 2) {
                    b7(abc, ab, n, k);
                    break;
                }
                res = b4(n, k);

                n -= res;
                b2(ab, ab + res - 1);
                ab += res;
                k -= ((res + 1) * (res + 1)) / 2;
                if (k == 0) {
                    break;
                }
            }
        }
    }
}

}