Submission #18178753


Source Code Expand

Copy
import java.io.InputStream;
import java.util.Arrays;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;

public class Main {
    public static void main(String[] args) throws Exception {
        ExtendedScanner sc = new ExtendedScanner();
        FastPrintStream pw = new FastPrintStream();
        solve(sc, pw);
        sc.close();
        pw.flush();
        pw.close();
    }

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        DSUForest dsu = new DSUForest(n);
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt() - 1;
            int y = sc.nextInt() - 1;
            dsu.merge(x, y);
        }
        Forest f = dsu.buildForest();
        int groupNum = f.groupNum();
        Tree[] ts = f.toTrees();
        EulerTourLCA[] lcas = new EulerTourLCA[groupNum];
        for (int i = 0; i < groupNum; i++) {
            lcas[i] = new EulerTourLCA(ts[i]);
        }
        int q = sc.nextInt();
        while (q --> 0) {
            int x = sc.nextInt() - 1;
            int y = sc.nextInt() - 1;
            int idx = f.id(x);
            int idy = f.id(y);
            if (idx != idy) {
                pw.println(-1);
                continue;
            }
            int ix = f.inv(x);
            int iy = f.inv(y);
            int ia = lcas[idx].query(ix, iy);
            int a = f.group(idx)[ia];
            pw.println(dsu.addedTime(a));
        }
    }
}


/**
 * @author https://atcoder.jp/users/suisen
 */
final class ExtendedScanner extends FastScanner {
    public ExtendedScanner() {super();}
    public ExtendedScanner(InputStream in) {super(in);}
    public int[] ints(final int n) {
        final int[] a = new int[n];
        Arrays.setAll(a, $ -> nextInt());
        return a;
    }
    public int[] ints(final int n, final IntUnaryOperator f) {
        final int[] a = new int[n];
        Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));
        return a;
    }
    public int[][] ints(final int n, final int m) {
        final int[][] a = new int[n][];
        Arrays.setAll(a, $ -> ints(m));
        return a;
    }
    public int[][] ints(final int n, final int m, final IntUnaryOperator f) {
        final int[][] a = new int[n][];
        Arrays.setAll(a, $ -> ints(m, f));
        return a;
    }
    public long[] longs(final int n) {
        final long[] a = new long[n];
        Arrays.setAll(a, $ -> nextLong());
        return a;
    }
    public long[] longs(final int n, final LongUnaryOperator f) {
        final long[] a = new long[n];
        Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));
        return a;
    }
    public long[][] longs(final int n, final int m) {
        final long[][] a = new long[n][];
        Arrays.setAll(a, $ -> longs(m));
        return a;
    }
    public long[][] longs(final int n, final int m, final LongUnaryOperator f) {
        final long[][] a = new long[n][];
        Arrays.setAll(a, $ -> longs(m, f));
        return a;
    }
    public char[][] charArrays(final int n) {
        final char[][] c = new char[n][];
        Arrays.setAll(c, $ -> nextChars());
        return c;
    }
    public double[] doubles(final int n) {
        final double[] a = new double[n];
        Arrays.setAll(a, $ -> nextDouble());
        return a;
    }
    public double[][] doubles(final int n, final int m) {
        final double[][] a = new double[n][];
        Arrays.setAll(a, $ -> doubles(m));
        return a;
    }
    public String[] strings(final int n) {
        final String[] s = new String[n];
        Arrays.setAll(s, $ -> next());
        return s;
    }
}

class Forest {
    final int n;
    final int groupNum;
    final int[][] adj;
    final int[] ids;
    final int[] inv;
    final int[] par;
    final int[][] groups;
    final int[] roots;
    final int[][] pre;
    final int[][] pst;
    Forest(int n, int[][] adj, int[][] groups, int[] ids, int[] inv, int[] root) {
        this.n = n;
        this.groupNum = groups.length;
        this.adj = adj;
        this.ids = ids;
        this.inv = inv;
        this.par = new int[n];
        this.groups = groups;
        this.roots = new int[groupNum];
        this.pre = new int[groupNum][];
        this.pst = new int[groupNum][];
        build(root);
    }
    private void build(int[] root) {
        int[] stack = new int[n << 1];
        java.util.Arrays.fill(par, -1);
        for (int i = 0; i < groupNum; i++) {
            int size = groups[i].length;
            int head = groups[i][0];
            roots[i] = root[head] < 0 ? head : root[head];
            int[] pre_i = pre[i] = new int[size];
            int[] pst_i = pst[i] = new int[size];
            int preOrd = 0, pstOrd = 0;
            int ptr = 0;
            stack[ptr++] = ~roots[i];
            stack[ptr++] =  roots[i];
            while (ptr > 0) {
                int u = stack[--ptr];
                if (u >= 0) {
                    pre_i[preOrd++] = u;
                    for (int v : adj[u]) {
                        if (v == par[u]) continue;
                        par[v] = u;
                        stack[ptr++] = ~v;
                        stack[ptr++] =  v;
                    }
                } else {
                    pst_i[pstOrd++] = ~u;
                }
            }
        }
    }
    public final int getV() {
        return n;
    }
    public final int groupNum() {
        return groupNum;
    }
    public final int[] edges(int u) {
        return adj[u];
    }
    public final int parent(int u) {
        return par[u];
    }
    public final int[] parent() {
        return par;
    }
    public final int[] ids() {
        return ids;
    }
    public final int[] invs() {
        return inv;
    }
    public final int id(int u) {
        return ids[u];
    }
    public final int inv(int u) {
        return inv[u];
    }
    public final int[] group(int id) {
        return groups[id];
    }
    public final int root(int id) {
        return roots[id];
    }
    public final int size(int id) {
        return groups[id].length;
    }
    public final int[] preOrder(int id) {
        return pre[id];
    }
    public final int[] postOrder(int id) {
        return pst[id];
    }
    public final Tree[] toTrees() {
        Tree[] ts = new Tree[groupNum];
        for (int id = 0; id < groupNum; id++) {
            int root = root(id);
            TreeBuilder tb = new TreeBuilder(size(id), inv[root]);
            for (int u : group(id)) {
                if (u != root) {
                    tb.addEdge(inv[u], inv[par[u]]);
                }
            }
            ts[id] = tb.build();
        }
        return ts;
    }
}


final class ForestBuilder {
    private final int[] dsu;
    private int t = 0;
    private final int[] time;
    private final int[] root;
    private final int n;
    private int ptr = 0;
    private final SimpleEdge[] edges;
    private final int[] count;
    public ForestBuilder(int n) {
        this.n = n;
        this.dsu = new int[n];
        java.util.Arrays.fill(dsu, -1);
        this.time = new int[n];
        this.root = new int[n];
        java.util.Arrays.fill(root, -1);
        this.edges = new SimpleEdge[n - 1];
        this.count = new int[n];
    }
    public void setRoot(int u) {
        root[leader(u)] = u;
        time[u] = ++t;
    }
    public void setRootIfAbsent(int u) {
        if (root[leader(u)] < 0) {
            root[leader(u)] = u;
            time[u] = ++t;
        }
    }
    public boolean isConnected(int u, int v) {
        return leader(u) == leader(v);
    }
    public int addEdgeIfDisconnected(int u, int v, long cost) {
        if (leader(u) != leader(v)) return addEdge(u, v);
        return -1;
    }
    public int addEdgeIfDisconnected(int u, int v) {
        return addEdgeIfDisconnected(u, v, 1);
    }
    public int addEdge(int u, int v, long cost) {
        if (leader(u) == leader(v)) throw new AssertionError();
        edges[ptr] = new SimpleEdge(u, v, cost);
        count[u]++;
        count[v]++;
        merge(u, v);
        return ptr++;
    }
    public int addEdge(int u, int v) {
        return addEdge(u, v, 1);
    }
    public Forest build() {
        int[][] adj = new int[n][];
        for (int i = 0; i < n; i++) adj[i] = new int[count[i]];
        for (int i = 0; i < ptr; i++) {
            int u = edges[i].from;
            int v = edges[i].to;
            adj[u][--count[u]] = v;
            adj[v][--count[v]] = u;
        }
        for (int i = 0; i < n; i++) root[i] = root[leader(i)];
        int[] inv = new int[n];
        int[] ids = new int[n];
        int[][] groups = groups(inv, ids);
        return new Forest(n, adj, groups, ids, inv, root);
    }

    public WeightedForest buildWeightedForest() {
        int[][] adj = new int[n][];
        long[][] cst = new long[n][];
        for (int i = 0; i < n; i++) {
            adj[i] = new int[count[i]];
            cst[i] = new long[count[i]];
        }
        for (int i = 0; i < ptr; i++) {
            int u = edges[i].from;
            int v = edges[i].to;
            adj[u][--count[u]] = v;
            adj[v][--count[v]] = u;
            cst[u][count[u]] = edges[i].cost;
            cst[v][count[v]] = edges[i].cost;
        }
        for (int i = 0; i < n; i++) root[i] = root[leader(i)];
        int[] inv = new int[n];
        int[] ids = new int[n];
        int[][] groups = groups(inv, ids);
        return new WeightedForest(n, adj, groups, ids, inv, root, cst);
    }

    private void merge(int x, int y) {
        if ((x = leader(x)) == (y = leader(y))) return;
        if (-dsu[x] < -dsu[y]) {int tmp = x; x = y; y = tmp;}
        dsu[x] += dsu[y];
        dsu[y] = x;
        int rx = root[x], ry = root[y];
        if (ry >= 0 && (rx < 0 || time[rx] < time[ry])) {
            root[x] = ry;
        }
    }
    private int leader(int x) {
        int p = dsu[x];
        return p < 0 ? x : (dsu[x] = leader(p));
    }
    private int[][] groups(int[] inv, int[] ids) {
        int[] cnt = new int[n];
        int groupNum = 0;
        for (int i = 0; i < n; i++) {
            if (dsu[i] < 0) cnt[ids[i] = groupNum++] = -dsu[i];
        }
        int[][] groups = new int[groupNum][];
        for (int j = 0; j < groupNum; j++) {
            groups[j] = new int[cnt[j]];
        }
        for (int i = 0; i < n; i++) {
            int j = ids[leader(i)];
            groups[ids[i] = j][inv[i] = --cnt[j]] = i;
        }
        return groups;
    }
}

/**
 * @author https://atcoder.jp/users/suisen
 */
class FastPrintStream implements AutoCloseable {
    private static final int INT_MAX_LEN = 11;
    private static final int LONG_MAX_LEN = 20;

    private int precision = 9;

    private static final int BUF_SIZE = 1 << 14;
    private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;
    private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;
    private final byte[] buf = new byte[BUF_SIZE];
    private int ptr = 0;
    private final java.lang.reflect.Field strField;
    private final java.nio.charset.CharsetEncoder encoder;

    private final java.io.OutputStream out;

    public FastPrintStream(java.io.OutputStream out) {
        this.out = out;
        java.lang.reflect.Field f;
        try {
            f = java.lang.String.class.getDeclaredField("value");
            f.setAccessible(true);
        } catch (NoSuchFieldException | SecurityException e) {
            f = null;
        }
        this.strField = f;
        this.encoder = java.nio.charset.StandardCharsets.US_ASCII.newEncoder();
    }

    public FastPrintStream(java.io.File file) throws java.io.IOException {
        this(new java.io.FileOutputStream(file));
    }

    public FastPrintStream(java.lang.String filename) throws java.io.IOException {
        this(new java.io.File(filename));
    }

    public FastPrintStream() {
        this(new java.io.FileOutputStream(java.io.FileDescriptor.out));
    }

    public FastPrintStream println() {
        if (ptr == BUF_SIZE) internalFlush();
        buf[ptr++] = (byte) '\n';
        return this;
    }

    public FastPrintStream println(java.lang.Object o) {
        return print(o).println();
    }

    public FastPrintStream println(java.lang.String s) {
        return print(s).println();
    }

    public FastPrintStream println(char[] s) {
        return print(s).println();
    }

    public FastPrintStream println(char c) {
        return print(c).println();
    }

    public FastPrintStream println(int x) {
        return print(x).println();
    }

    public FastPrintStream println(long x) {
        return print(x).println();
    }

    public FastPrintStream println(double d, int precision) {
        return print(d, precision).println();
    }

    public FastPrintStream println(double d) {
        return print(d).println();
    }

    private FastPrintStream print(byte[] bytes) {
        int n = bytes.length;
        if (ptr + n > BUF_SIZE) {
            internalFlush();
            try {
                out.write(bytes);
            } catch (java.io.IOException e) {
                throw new java.io.UncheckedIOException(e);
            }
        } else {
            System.arraycopy(bytes, 0, buf, ptr, n);
            ptr += n;
        }
        return this;
    }

    public FastPrintStream print(java.lang.Object o) {
        return print(o.toString());
    }

    public FastPrintStream print(java.lang.String s) {
        if (strField == null) {
            return print(s.getBytes());
        } else {
            try {
                Object value = strField.get(s);
                if (value instanceof byte[]) {
                    return print((byte[]) value);
                } else {
                    return print((char[]) value);
                }
            } catch (IllegalAccessException e) {
                return print(s.getBytes());
            }
        }
    }

    public FastPrintStream print(char[] s) {
        try {
            return print(encoder.encode(java.nio.CharBuffer.wrap(s)).array());
        } catch (java.nio.charset.CharacterCodingException e) {
            byte[] bytes = new byte[s.length];
            for (int i = 0; i < s.length; i++) {
                bytes[i] = (byte) s[i];
            }
            return print(bytes);
        }
    }

    public FastPrintStream print(char c) {
        if (ptr == BUF_SIZE) internalFlush();
        buf[ptr++] = (byte) c;
        return this;
    }

    public FastPrintStream print(int x) {
        if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();
        if (-10 < x && x < 10) {
            if (x < 0) {
                buf[ptr++] = '-';
                x = -x;
            }
            buf[ptr++] = (byte) ('0' + x);
            return this;
        }
        int d;
        if (x < 0) {
            if (x == Integer.MIN_VALUE) {
                buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';
                buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';
                buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';
                return this;
            }
            d = len(x = -x);
            buf[ptr++] = '-';
        } else {
            d = len(x);
        }
        int j = ptr += d; 
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        return this;
    }

    public FastPrintStream print(long x) {
        if ((int) x == x) return print((int) x);
        if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();
        int d;
        if (x < 0) {
            if (x == Long.MIN_VALUE) {
                buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';
                buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';
                buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';
                buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';
                buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';
                return this;
            }
            d = len(x = -x);
            buf[ptr++] = '-';
        } else {
            d = len(x);
        }
        int j = ptr += d; 
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        return this;
    }

    public FastPrintStream print(double d, int precision) {
        if (d < 0) {
            print('-');
            d = -d;
        }
        d += Math.pow(10, -precision) / 2;
        print((long) d).print('.');
        d -= (long) d;
        for(int i = 0; i < precision; i++){
            d *= 10;
            print((int) d);
            d -= (int) d;
        }
        return this;
    }

    public FastPrintStream print(double d) {
        return print(d, precision);
    }

    public void setPrecision(int precision) {
        this.precision = precision;
    }

    private void internalFlush() {
        try {
            out.write(buf, 0, ptr);
            ptr = 0;
        } catch (java.io.IOException e) {
            throw new java.io.UncheckedIOException(e);
        }
    }

    public void flush() {
        try {
            out.write(buf, 0, ptr);
            out.flush();
            ptr = 0;
        } catch (java.io.IOException e) {
            throw new java.io.UncheckedIOException(e);
        }
    }

    public void close() {
        try {
            out.close();
        } catch (java.io.IOException e) {
            throw new java.io.UncheckedIOException(e);
        }
    }

    private static int len(int x) {
        return
            x >= 1000000000 ? 10 :
            x >= 100000000  ?  9 :
            x >= 10000000   ?  8 :
            x >= 1000000    ?  7 :
            x >= 100000     ?  6 :
            x >= 10000      ?  5 :
            x >= 1000       ?  4 :
            x >= 100        ?  3 :
            x >= 10         ?  2 : 1;
    }

    private static int len(long x) {
        return
            x >= 1000000000000000000l ? 19 :
            x >= 100000000000000000l  ? 18 :
            x >= 10000000000000000l   ? 17 :
            x >= 1000000000000000l    ? 16 :
            x >= 100000000000000l     ? 15 :
            x >= 10000000000000l      ? 14 :
            x >= 1000000000000l       ? 13 :
            x >= 100000000000l        ? 12 :
            x >= 10000000000l         ? 11 : 10;
    }
}
/**
 * @author https://atcoder.jp/users/suisen
 */
class Tree {
    final int n;
    final int root;
    final int[][] adj;
    final int[] par;
    final int[] pre;
    final int[] pst;
    Tree(int n, int root, int[][] adj) {
        this.n = n;
        this.adj = adj;
        this.root = root;
        this.par = new int[n];
        this.pre = new int[n];
        this.pst = new int[n];
        build();
    }
    private void build() {
        int preOrd = 0, pstOrd = 0;
        java.util.Arrays.fill(par, -1);
        int[] stack = new int[n << 1];
        int ptr = 0;
        stack[ptr++] = ~root;
        stack[ptr++] =  root;
        while (ptr > 0) {
            int u = stack[--ptr];
            if (u >= 0) {
                pre[preOrd++] = u;
                for (int v : adj[u]) {
                    if (v == par[u]) continue;
                    par[v] = u;
                    stack[ptr++] = ~v;
                    stack[ptr++] =  v;
                }
            } else {
                pst[pstOrd++] = ~u;
            }
        }
    }
    public int getV() {
        return n;
    }
    public int getRoot() {
        return root;
    }
    public int[] getEdges(int u) {
        return adj[u];
    }
    public int[] parent() {
        return par;
    }
    public int[] preOrder() {
        return pre;
    }
    public int[] postOrder() {
        return pst;
    }
}
/**
 * @author https://atcoder.jp/users/suisen
 */
class WeightedTree extends Tree {
    final long[] cst;
    final long[][] adjCost;
    WeightedTree(int n, int root, int[][] adj, long[][] adjCost) {
        super(n, root, adj);
        this.cst = new long[n];
        this.adjCost = adjCost;
        for (int u = 0; u < n; u++) {
            int k = adj[u].length;
            for (int i = 0; i < k; i++) {
                int v = adj[u][i];
                long c = adjCost[u][i];
                if (v == par[u]) {
                    cst[u] = c;
                } else {
                    cst[v] = c;
                }
            }
        }
    }
    public long[] getWeights() {
        return cst;
    }
    public long getWeight(int u, int i) {
        return adjCost[u][i];
    }
}


class DSUForest {
    final int N;
    final int[] Dat;

    final int M;
    final ForestBuilder fb;
    final int[] SubtreeRoot;
    final int[] time;
    int now = 0;
    int idx;
    public DSUForest(int n) {
        this.N = n;
        this.Dat = new int[N];
        java.util.Arrays.fill(Dat, -1);

        this.M = 2 * N - 1;
        this.fb = new ForestBuilder(M);
        this.SubtreeRoot = new int[N];
        this.time = new int[M];
        this.idx = N;
        java.util.Arrays.setAll(SubtreeRoot, i -> i);
        java.util.Arrays.fill(time, N, M, Integer.MAX_VALUE);
    }
    public int merge(int x, int y) {
        now++;
        x = leader(x); y = leader(y);
        if (x == y) return now;
        if (-Dat[x] < -Dat[y]) {int tmp = x; x = y; y = tmp;}
        Dat[x] += Dat[y];
        Dat[y] = x;
        fb.addEdge(SubtreeRoot[x], idx);
        fb.addEdge(SubtreeRoot[y], idx);
        SubtreeRoot[x] = idx;
        return time[idx++] = now;
    }
    public int addedTime(int node) {
        return time[node];
    }
    public boolean same(int x, int y) {
        return leader(x) == leader(y);
    }
    public int leader(int x) {
        if (Dat[x] < 0) return x;
        return Dat[x] = leader(Dat[x]);
    }
    public int size(int x) {
        return -Dat[leader(x)];
    }
    public int[][] groups() {
        int[] cmp = new int[N];
        int[] cnt = new int[N];
        int groupNum = 0;
        for (int i = 0; i < N; i++) {
            if (Dat[i] < 0) {
                cnt[cmp[i] = groupNum++] = -Dat[i];
            }
        }
        int[][] groups = new int[groupNum][];
        for (int j = 0; j < groupNum; j++) {
            groups[j] = new int[cnt[j]];
        }
        for (int i = 0; i < N; i++) {
            int j = cmp[leader(i)];
            groups[j][--cnt[j]] = i;
        }
        return groups;
    }
    public Forest buildForest() {
        return fb.build();
    }
}


class TreeBuilder {
    private final int n;
    private int ptr = 0;
    private final int root;
    private final SimpleEdge[] edges;
    private final int[] count;
    public TreeBuilder(int n, int root) {
        this.n = n;
        this.root = root;
        this.edges = new SimpleEdge[n - 1];
        this.count = new int[n];
    }
    public TreeBuilder(int n) {
        this(n, 0);
    }
    public int addEdge(int u, int v, long cost) {
        edges[ptr] = new SimpleEdge(u, v, cost);
        count[u]++;
        count[v]++;
        return ptr++;
    }
    public int addEdge(int u, int v) {
        return addEdge(u, v, 1);
    }
    public SimpleEdge[] getEdges() {
        if (ptr < n - 1) throw new NullPointerException("too few edges.");
        return edges;
    }
    public Tree build() {
        int[][] adj = new int[n][];
        for (int i = 0; i < n; i++) {
            adj[i] = new int[count[i]];
        }
        for (SimpleEdge e : edges) {
            int u = e.from;
            int v = e.to;
            adj[u][--count[u]] = v;
            adj[v][--count[v]] = u;
        }
        return new Tree(n, root, adj);
    }
    public WeightedTree buildWeightedTree() {
        int[][] adj = new int[n][];
        long[][] cst = new long[n][];
        for (int i = 0; i < n; i++) {
            adj[i] = new int[count[i]];
            cst[i] = new long[count[i]];
        }
        for (SimpleEdge e : edges) {
            int u = e.from;
            int v = e.to;
            adj[u][--count[u]] = v;
            adj[v][--count[v]] = u;
            cst[u][count[u]] = e.cost;
            cst[v][count[v]] = e.cost;
        }
        return new WeightedTree(n, root, adj, cst);
    }
}

/**
 * @author https://atcoder.jp/users/suisen
 */
class FastScanner implements AutoCloseable {
    private final ByteBuffer tokenBuf = new ByteBuffer();
    private final java.io.InputStream in;
    private final byte[] rawBuf = new byte[1 << 14];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner(java.io.InputStream in) {
        this.in = in;
    }

    public FastScanner() {
        this(new java.io.FileInputStream(java.io.FileDescriptor.in));
    }

    private final int readByte() {
        if (ptr < buflen) return rawBuf[ptr++];
        ptr = 0;
        try {
            buflen = in.read(rawBuf);
            if (buflen > 0) {
                return rawBuf[ptr++];
            } else {
                throw new java.io.EOFException();
            }
        } catch (java.io.IOException e) {
            throw new java.io.UncheckedIOException(e);
        }
    }

    private final int readByteUnsafe() {
        if (ptr < buflen) return rawBuf[ptr++];
        ptr = 0;
        try {
            buflen = in.read(rawBuf);
            if (buflen > 0) {
                return rawBuf[ptr++];
            } else {
                return -1;
            }
        } catch (java.io.IOException e) {
            throw new java.io.UncheckedIOException(e);
        }
    }

    private final int skipUnprintableChars() {
        int b = readByte();
        while (b <= 32 || b >= 127) b = readByte();
        return b;
    }

    private final void loadToken() {
        tokenBuf.clear();
        for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) {
            tokenBuf.append(b);
        }
    }

    public final boolean hasNext() {
        for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) {
            if (b == -1) return false;
        }
        --ptr;
        return true;
    }

    public final String next() {
        loadToken();
        return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
    }

    public final String nextLine() {
        tokenBuf.clear();
        for (int b = readByte(); b != '\n'; b = readByteUnsafe()) {
            if (b == -1) break;
            tokenBuf.append(b);
        }
        return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
    }

    public final char nextChar() {
        return (char) skipUnprintableChars();
    }

    public final char[] nextChars() {
        loadToken();
        return tokenBuf.toCharArray();
    }

    public final long nextLong() {
        long n = 0;
        boolean isNegative = false;
        int b = skipUnprintableChars();
        if (b == '-') {
            isNegative = true;
            b = readByteUnsafe();
        }
        if (b < '0' || '9' < b) throw new NumberFormatException();
        while ('0' <= b && b <= '9') {
            // -9223372036854775808 - 9223372036854775807
            if (n >= 922337203685477580l) {
                if (n > 922337203685477580l) {
                    throw new ArithmeticException("long overflow");
                }
                if (isNegative) {
                    if (b >= '9') {
                        throw new ArithmeticException("long overflow");
                    }
                    n = -n - (b + '0');
                    b = readByteUnsafe();
                    if ('0' <= b && b <= '9') {
                        throw new ArithmeticException("long overflow");
                    } else if (b <= 32 || b >= 127) {
                        return n;
                    } else {
                        throw new NumberFormatException();
                    }
                } else {
                    if (b >= '8') {
                        throw new ArithmeticException("long overflow");
                    }
                    n = n * 10 + b - '0';
                    b = readByteUnsafe();
                    if ('0' <= b && b <= '9') {
                        throw new ArithmeticException("long overflow");
                    } else if (b <= 32 || b >= 127) {
                        return n;
                    } else {
                        throw new NumberFormatException();
                    }
                }
            }
            n = n * 10 + b - '0';
            b = readByteUnsafe();
        }
        if (b <= 32 || b >= 127) return isNegative ? -n : n;
        throw new NumberFormatException();
    }
    public final int nextInt() {
        long value = nextLong();
        if ((int) value != value) {
            throw new ArithmeticException("int overflow");
        }
        return (int) value;
    }
    public final double nextDouble() {
        return Double.parseDouble(next());
    }
    public final void close() {
        try {
            in.close();
        } catch (java.io.IOException e) {
            throw new java.io.UncheckedIOException(e);
        }
    }

    private static final class ByteBuffer {
        private static final int DEFAULT_BUF_SIZE = 1 << 12;
        private byte[] buf;
        private int ptr = 0;
        private ByteBuffer(int capacity) {
            this.buf = new byte[capacity];
        }
        private ByteBuffer() {
            this(DEFAULT_BUF_SIZE);
        }
        private ByteBuffer append(int b) {
            if (ptr == buf.length) {
                int newLength = buf.length << 1;
                byte[] newBuf = new byte[newLength];
                System.arraycopy(buf, 0, newBuf, 0, buf.length);
                buf = newBuf;
            }
            buf[ptr++] = (byte) b;
            return this;
        }
        private char[] toCharArray() {
            char[] chs = new char[ptr];
            for (int i = 0; i < ptr; i++) {
                chs[i] = (char) buf[i];
            }
            return chs;
        }
        private byte[] getRawBuf() {
            return buf;
        }
        private int size() {
            return ptr;
        }
        private void clear() {
            ptr = 0;
        }
    }
}
/**
 * @verified
 * - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
 * - https://atcoder.jp/contests/abc014/tasks/abc014_4
 */
class EulerTourLCA {
    private final int n;
    private final int[] tour;
    private final int[] tbeg;
    private final int[] dep;
    private final int m;
    private final int[] seg;
    public EulerTourLCA(Tree t) {
        this.n = t.getV();
        this.tour = new int[2 * n];
        this.tbeg = new int[n];
        this.dep = new int[n];
        dfs(t);
        int k = 1;
        while (k < n << 1) k <<= 1;
        this.m = k;
        this.seg = new int[m << 1];
        buildSegTree();
    }
    private void dfs(Tree t) {
        int k = 0;
        int[] par = t.parent();
        int[] stack = new int[n << 1];
        int ptr = 0;
        int root = t.getRoot();
        stack[ptr++] = ~root;
        stack[ptr++] =  root;
        while (ptr > 0) {
            int u = stack[--ptr];
            if (u >= 0) {
                tour[tbeg[u] = k++] = u;
                for (int v : t.getEdges(u)) {
                    if (v == par[u]) continue;
                    dep[v] = dep[u] + 1;
                    stack[ptr++] = ~v;
                    stack[ptr++] =  v;
                }
            } else {
                tour[k++] = par[~u];
            }
        }
    }
    private void buildSegTree() {
        for (int i = 0; i < 2 * n - 1; i++) {
            seg[i + m] = dep[tour[i]];
        }
        java.util.Arrays.fill(seg, m + 2 * n - 1, 2 * m, n);
        for (int i = m - 1; i > 0; i--) {
            seg[i] = Math.min(seg[i << 1 | 0], seg[i << 1 | 1]);
        }
    }
    public int query(int u, int v) {
        if (tbeg[u] > tbeg[v]) return query(v, u);
        int mink = -1, min = n;
        for (int l = tbeg[u] + m, r = tbeg[v] + m + 1; l < r; l >>= 1, r >>= 1) {
            if ((l & 1) == 1) {
                if (seg[l] < min) min = seg[mink = l];
                l++;
            }
            if ((r & 1) == 1) {
                r--;
                if (seg[r] < min) min = seg[mink = r];
            }
        }
        while (mink < m) {
            mink <<= 1;
            if (min != seg[mink]) mink |= 1;
        }
        return tour[mink - m];
    }
    public int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[query(u, v)];
    }
}

final class SimpleEdge extends AbstractEdge {
    public SimpleEdge(int from, int to, long cost) {
        super(from, to, cost);
    }
    public SimpleEdge(int from, int to) {
        super(from, to);
    }
    @Override
    public SimpleEdge reverse() {
        return new SimpleEdge(to, from, cost);
    }
}

abstract class AbstractEdge implements Comparable<AbstractEdge> {
    public final int from, to;
    public final long cost;
    public AbstractEdge(int from, int to, long cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
    public AbstractEdge(int from, int to) {
        this(from, to, 1l);
    }
    public abstract AbstractEdge reverse();
    public int compareTo(AbstractEdge o) {
        return Long.compare(cost, o.cost);
    }
}

class WeightedForest extends Forest {
    final long[] cst;
    final long[][] adjCost;

    WeightedForest(int n, int[][] adj, int[][] groups, int[] ids, int[] inv, int[] root, long[][] adjCost) {
        super(n, adj, groups, ids, inv, root);
        this.cst = new long[n];
        this.adjCost = adjCost;
        for (int u = 0; u < n; u++) {
            int k = adj[u].length;
            for (int i = 0; i < k; i++) {
                int v = adj[u][i];
                long c = adjCost[u][i];
                if (v == par[u]) {
                    cst[u] = c;
                } else {
                    cst[v] = c;
                }
            }
        }
    }
    public long[] getWeights() {
        return cst;
    }
    public long getWeight(int u, int i) {
        return adjCost[u][i];
    }
}

Submission Info

Submission Time
Task H - Union Sets
User suisen
Language Java (OpenJDK 11.0.6)
Score 600
Code Size 35473 Byte
Status AC
Exec Time 509 ms
Memory 140036 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 49
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 95 ms 34176 KB
sample_02.txt AC 93 ms 34504 KB
sample_03.txt AC 88 ms 34084 KB
subtask_1_1.txt AC 86 ms 34244 KB
subtask_1_10.txt AC 134 ms 35016 KB
subtask_1_11.txt AC 180 ms 39680 KB
subtask_1_12.txt AC 288 ms 89208 KB
subtask_1_13.txt AC 99 ms 34432 KB
subtask_1_14.txt AC 87 ms 34152 KB
subtask_1_15.txt AC 128 ms 35752 KB
subtask_1_16.txt AC 107 ms 34696 KB
subtask_1_17.txt AC 101 ms 35176 KB
subtask_1_18.txt AC 92 ms 34248 KB
subtask_1_19.txt AC 263 ms 77156 KB
subtask_1_2.txt AC 87 ms 34272 KB
subtask_1_20.txt AC 85 ms 34436 KB
subtask_1_21.txt AC 106 ms 35032 KB
subtask_1_22.txt AC 203 ms 63520 KB
subtask_1_23.txt AC 491 ms 139320 KB
subtask_1_24.txt AC 472 ms 139512 KB
subtask_1_25.txt AC 503 ms 140036 KB
subtask_1_26.txt AC 480 ms 137964 KB
subtask_1_27.txt AC 486 ms 94424 KB
subtask_1_28.txt AC 504 ms 94172 KB
subtask_1_29.txt AC 477 ms 138808 KB
subtask_1_3.txt AC 93 ms 34352 KB
subtask_1_30.txt AC 482 ms 138744 KB
subtask_1_31.txt AC 482 ms 139504 KB
subtask_1_32.txt AC 495 ms 137920 KB
subtask_1_33.txt AC 488 ms 94384 KB
subtask_1_34.txt AC 491 ms 94796 KB
subtask_1_35.txt AC 489 ms 139456 KB
subtask_1_36.txt AC 485 ms 138348 KB
subtask_1_37.txt AC 499 ms 139832 KB
subtask_1_38.txt AC 495 ms 139420 KB
subtask_1_39.txt AC 495 ms 95076 KB
subtask_1_4.txt AC 383 ms 101084 KB
subtask_1_40.txt AC 509 ms 95728 KB
subtask_1_41.txt AC 133 ms 34948 KB
subtask_1_42.txt AC 139 ms 35240 KB
subtask_1_43.txt AC 378 ms 78108 KB
subtask_1_44.txt AC 462 ms 94400 KB
subtask_1_45.txt AC 127 ms 35028 KB
subtask_1_46.txt AC 489 ms 139400 KB
subtask_1_5.txt AC 109 ms 34832 KB
subtask_1_6.txt AC 297 ms 89312 KB
subtask_1_7.txt AC 115 ms 42160 KB
subtask_1_8.txt AC 139 ms 49620 KB
subtask_1_9.txt AC 138 ms 45828 KB