Let u and v be two distinct vertices in a direct...

Here’s a Java solution that runs in $O(n)$ per test case by using a two-pass “rerooting” DP to compute, for every node $r$, the sum of distances

In a tree oriented as an arborescence away from $r$, the number of good pairs is exactly $S(r)$. We look for a node $r$ with $S(r)=n$. If found, we root the tree at $r$, direct every edge away from $r$, and print “YES” plus that orientation. Otherwise we print “NO.”

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

public class Main {
    static int n;
    static List<Integer>[] g;
    static long[] depth, sz, distSum;
    static int[] parent0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            n = Integer.parseInt(br.readLine().trim());
            g = new ArrayList[n+1];
            for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
            for (int i = 0; i < n-1; i++) {
                String[] uv = br.readLine().split(" ");
                int u = Integer.parseInt(uv[0]);
                int v = Integer.parseInt(uv[1]);
                g[u].add(v);
                g[v].add(u);
            }
            if (n == 2) {
                // Only one edge → only 1 good pair possible
                out.println("NO");
                continue;
            }
            // 1) First DFS from node 1 to compute depth[] and subtree sizes sz[]
            depth = new long[n+1];
            sz    = new long[n+1];
            parent0 = new int[n+1];
            dfs1(1);
            // initial sum of distances from 1:
            long initSum = 0;
            for (int i = 1; i <= n; i++) initSum += depth[i];
            // 2) Reroot DP to compute distSum[r] for all r
            distSum = new long[n+1];
            distSum[1] = initSum;
            dfsReroot(1);
            // 3) Find a node r with distSum[r] == n
            int goodRoot = -1;
            for (int i = 1; i <= n; i++) {
                if (distSum[i] == n) {
                    goodRoot = i;
                    break;
                }
            }
            if (goodRoot == -1) {
                out.println("NO");
            } else {
                out.println("YES");
                // 4) BFS from goodRoot to orient every edge away from it
                Queue<Integer> q = new ArrayDeque<>();
                int[] parentR = new int[n+1];
                parentR[goodRoot] = 0;
                q.add(goodRoot);
                StringBuilder sb = new StringBuilder();
                while (!q.isEmpty()) {
                    int u = q.poll();
                    for (int v : g[u]) {
                        if (v == parentR[u]) continue;
                        parentR[v] = u;
                        // direct edge u->v
                        sb.append(u).append(' ').append(v).append('\n');
                        q.add(v);
                    }
                }
                // Print the n-1 directed edges
                out.print(sb);
            }
        }
        out.flush();
    }

    // Iterative two-phase DFS to get depth[] and subtree sizes sz[]
    static void dfs1(int root) {
        class Frame { int u, p; boolean post; }
        Deque<Frame> st = new ArrayDeque<>();
        depth[root] = 0;
        parent0[root] = 0;
        st.push(new Frame(){ {u = root; p = 0; post = false;} });
        while (!st.isEmpty()) {
            Frame f = st.pop();
            int u = f.u, p = f.p;
            if (f.post) {
                // post-order: compute size[u]
                sz[u] = 1;
                for (int v : g[u]) {
                    if (v == p) continue;
                    sz[u] += sz[v];
                }
            } else {
                // pre-order
                parent0[u] = p;
                // push post-frame
                st.push(new Frame(){ {u = u; p = p; post = true;} });
                // push children
                for (int v : g[u]) {
                    if (v == p) continue;
                    depth[v] = depth[u] + 1;
                    st.push(new Frame(){ {u = v; p = u; post = false;} });
                }
            }
        }
    }

    // DFS to reroot distances: distSum[v] = distSum[u] + n - 2*sz[v]
    static void dfsReroot(int root) {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(root);
        while (!st.isEmpty()) {
            int u = st.pop();
            for (int v : g[u]) {
                if (v == parent0[u]) continue;
                parent0[v] = u;  // keep following the initial tree structure
                distSum[v] = distSum[u] + n - 2L*sz[v];
                st.push(v);
            }
        }
    }
}

Explanation of key steps

1. Compute depths & subtree-sizes
   We run an iterative “two-phase” DFS from node 1. On the way down (pre-order) we set depth[v] = depth[u] + 1. On the way back up (post-order) we sum children’s sizes to get the subtree size sz[u].

2. Initial sum of distances

   $$S(1) \;=\;\sum_{v=1}^n \mathrm{depth}[v].$$

3. Reroot DP
   There is a classic identity for trees: if you move the root from u to its child v, the sum of distances changes by

   $$S(v) \;=\; S(u)\;+\;n \;-\;2\,\text{sz}[v].$$

   We do a second DFS (again iterative) along the same parent pointers to fill distSum[v] for every node.

4. Check for target
   We scan for any node r with distSum[r] == n. Orienting all edges away from r yields exactly n good pairs.

5. Output
   If no such r exists, print “NO”. Otherwise print “YES” and then do a BFS from r, directing every tree edge from parent to child (this produces an arborescence rooted at r with exactly n good pairs).