Qn: Let u and v be two distinct vertices in a di...

Here’s a Java solution that runs in $O(n)$ per test and uses two rooted DFS’s from the degree-2 “center” to orient all non-spine edges in an alternating fashion so that no extra length-2 (or longer) reachability appears outside the single spine path:

java
import java.io.*;
import java.util.*;

public class Main {
    static class Edge { int u, v; Edge(int u, int v){ this.u = u; this.v = v; } }
    static int n;
    static List<Integer>[] adj;
    static List<Edge> ans;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int t = Integer.parseInt(in.readLine().trim());
        while (t-- > 0) {
            n = Integer.parseInt(in.readLine().trim());
            adj = new ArrayList[n+1];
            for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
            for (int i = 0; i < n-1; i++) {
                String[] uv = in.readLine().split(" ");
                int u = Integer.parseInt(uv[0]), v = Integer.parseInt(uv[1]);
                adj[u].add(v);
                adj[v].add(u);
            }
            // find a node of degree 2
            int center = -1;
            for (int i = 1; i <= n; i++) {
                if (adj[i].size() == 2) {
                    center = i;
                    break;
                }
            }
            if (center == -1) {
                out.println("NO");
                continue;
            }

            // the two neighbors on the spine
            int a = adj[center].get(0);
            int b = adj[center].get(1);

            ans = new ArrayList<>(n-1);
            // orient the spine: a -> center -> b
            ans.add(new Edge(a, center));
            ans.add(new Edge(center, b));

            // DFS from a, skipping center
            dfsOrient(a, center);
            // DFS from b, skipping center
            dfsOrient(b, center);

            out.println("YES");
            StringBuilder sb = new StringBuilder();
            for (Edge e : ans) {
                sb.append(e.u).append(' ').append(e.v).append('\n');
            }
            out.print(sb);
        }
        out.flush();
    }

    // iterative DFS from root, skipping the given 'block' parent on first step,
    // orienting edges in alternating fashion: at odd depth, child->parent; even depth, parent->child
    static void dfsOrient(int root, int block) {
        Deque<int[]> stack = new ArrayDeque<>();
        // push all true children of root (i.e. neighbors ≠ block) at depth=1
        for (int nei : adj[root]) {
            if (nei == block) continue;
            stack.push(new int[]{nei, root, 1});
        }
        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            int u = cur[0], p = cur[1], d = cur[2];
            // orient edge (p,u)
            if ((d & 1) == 1) {
                // odd depth → child->parent
                ans.add(new Edge(u, p));
            } else {
                // even depth → parent->child
                ans.add(new Edge(p, u));
            }
            // recurse
            for (int v : adj[u]) {
                if (v == p) continue;
                stack.push(new int[]{v, u, d+1});
            }
        }
    }
}

Explanation of the key steps:

1. Find a “center” vertex of degree 2.
   If no vertex has degree exactly 2, you can’t create exactly one extra length-2 reachable pair beyond the $n-1$ direct edges, so the answer is NO.

2. Spine orientation.
   Let the two neighbors of the center be $a$ and $b$. Orient the unique 3-node spine

   $$a \;\longrightarrow\; \text{center} \;\longrightarrow\; b$$

   This yields exactly one extra reachable pair $(a,b)$.

3. Orient each non-spine subtree by alternating edge‐directions.

   • Run two separate DFS’s, one from $a$ (skipping the edge back to the center) and one from $b$.
   • Number the DFS levels starting at 1 for the first edge. For an edge at odd depth, direct it child→parent; at even depth, direct it parent→child.
   • This guarantees each subtree edge contributes exactly one reachable pair (the edge itself), and prevents any two consecutive edges in a path from aligning in the same direction—so no unintended length-2 (or longer) reachability is introduced.

Together, you get exactly $(n-1)$ from the edges themselves plus the single $(a,b)$ through the spine, for a total of $n$ good pairs.