You are given a tree∗ with n vertices numbered f...

Here’s a clean Java solution that picks a valid first sliding operation from an optimal sequence. It:

• Finds a tree diameter (two BFS).
• Walks along the diameter path and looks for the first node with degree ≥ 3.
• Chooses c as the neighbor towards one diameter endpoint and a as the other path neighbor (so sliding at b pushes all off-path branches along the diameter in one direction).
• If no such node exists, the tree is already a path ⇒ print -1.

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

/**
 * Tree → Path (first optimal sliding move)
 *
 * For each test case:
 *  - If max degree ≤ 2, it's already a path -> print -1.
 *  - Otherwise:
 *      * Find a diameter path using two BFS runs.
 *      * On that path (excluding one endpoint), find the first node b with deg[b] ≥ 3.
 *      * Let c be the path neighbor of b towards the chosen endpoint of the diameter.
 *      * Let a be the other path neighbor (if exists); otherwise pick any other neighbor (safe guard).
 *      * Output: a b c
 */
public class Main {
    static class FastScanner {
      private final InputStream in;
      private final byte[] buffer = new byte[1 << 16];
      private int ptr = 0, len = 0;
      FastScanner(InputStream is) { in = is; }
      private int read() throws IOException {
        if (ptr >= len) {
          len = in.read(buffer);
          ptr = 0;
          if (len <= 0) return -1;
        }
        return buffer[ptr++];
      }
      int nextInt() throws IOException {
        int c, sgn = 1, x = 0;
        do { c = read(); } while (c <= ' ' && c != -1);
        if (c == '-') { sgn = -1; c = read(); }
        while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
        return x * sgn;
      }
    }

    static class BFSResult {
        int far;
        int[] parent;
        int[] dist;
        BFSResult(int far, int[] parent, int[] dist) {
            this.far = far; this.parent = parent; this.dist = dist;
        }
    }

    static BFSResult bfs(int n, List<Integer>[] g, int start) {
        int[] dist = new int[n + 1];
        int[] par = new int[n + 1];
        Arrays.fill(dist, -1);
        Arrays.fill(par, -1);
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(start);
        dist[start] = 0;
        int far = start;

        while (!q.isEmpty()) {
            int u = q.poll();
            if (dist[u] > dist[far]) far = u;
            for (int v : g[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    par[v] = u;
                    q.add(v);
                }
            }
        }
        return new BFSResult(far, par, dist);
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();
        int T = fs.nextInt();
        while (T-- > 0) {
            int n = fs.nextInt();
            @SuppressWarnings("unchecked")
            List<Integer>[] g = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
            int[] deg = new int[n + 1];

            for (int i = 0; i < Math.max(0, n - 1); i++) {
                int u = fs.nextInt(), v = fs.nextInt();
                g[u].add(v); g[v].add(u);
                deg[u]++; deg[v]++;
            }

            if (n <= 2) { // 1 node or single edge is already a path
                out.append("-1\n");
                continue;
            }

            int maxDeg = 0;
            for (int i = 1; i <= n; i++) maxDeg = Math.max(maxDeg, deg[i]);
            if (maxDeg <= 2) {
                out.append("-1\n");
                continue; // already a path graph
            }

            // Find diameter path
            int any = 1;
            BFSResult r1 = bfs(n, g, any);
            int u = r1.far;
            BFSResult r2 = bfs(n, g, u);
            int v = r2.far;

            // Reconstruct path u -> v using parent from r2
            List<Integer> path = new ArrayList<>();
            for (int cur = v; cur != -1; cur = r2.parent[cur]) path.add(cur);
            Collections.reverse(path); // path[0] == u, path[last] == v

            // Choose endpoint to push towards (use u = path.get(0))
            int endpoint = path.get(0);

            // Find first node b on the path (excluding endpoint) with degree >= 3
            // We'll iterate indices 1..len-2 (internal nodes); diameter endpoints are leaves in a tree.
            int len = path.size();
            int b = -1, a = -1, c = -1;

            for (int i = 1; i <= len - 2; i++) {
                int node = path.get(i);
                if (deg[node] >= 3) {
                    b = node;
                    // c = neighbor towards endpoint (previous on path)
                    c = path.get(i - 1);
                    // a = other path neighbor (next on path)
                    a = path.get(i + 1);
                    break;
                }
            }

            // Safety fallback (shouldn't be needed if maxDeg>2, since a branching off the diameter
            // must raise a path node's degree). Still, handle rare edge cases.
            if (b == -1) {
                // Check endpoints in case something weird happens (shouldn't for tree diameter)
                // Try the far endpoint side (index len-1) if its degree >= 3.
                int idx = len - 1;
                int node = path.get(idx);
                if (deg[node] >= 3) {
                    b = node;
                    c = path.get(idx - 1);
                    // pick any neighbor of b different from c
                    for (int nei : g[b]) { if (nei != c) { a = nei; break; } }
                }
            }

            if (b == -1) {
                // If we still didn't find it, consider the start endpoint (index 0) similarly.
                int idx = 0;
                int node = path.get(idx);
                if (deg[node] >= 3) {
                    b = node;
                    c = path.get(idx + 1);
                    for (int nei : g[b]) { if (nei != c) { a = nei; break; } }
                }
            }

            if (b == -1) {
                // As a final guard, but realistically won't happen given maxDeg>2
                out.append("-1\n");
            } else {
                out.append(a).append(' ').append(b).append(' ').append(c).append('\n');
            }
        }
        System.out.print(out.toString());
    }
}

How it works (quickly): we orient along a diameter and “push” all extra branches from each diameter node b towards a fixed endpoint via the neighbor c on the diameter. One sliding operation per such b is necessary and sufficient; any order works, so picking the first such b yields a valid first move in an optimal sequence.