Contest Duration: - (local time) (180 minutes)

Submission #18178814

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), idy = f.id(y);
if (idx != idy) {
pw.println(-1);
continue;
}
int node = f.get(idx, lcas[idx].query(f.index(x), f.index(y)));
}
}
}

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++;
if (x == y) return now;
if (-Dat[x] < -Dat[y]) {int tmp = x; x = y; y = tmp;}
Dat[x] += Dat[y];
Dat[y] = x;
SubtreeRoot[x] = idx;
return Time[idx++] = now;
}
return Time[node];
}
public boolean same(int x, int y) {
}
if (Dat[x] < 0) return x;
}
public int size(int 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++) {
groups[j][--cnt[j]] = i;
}
return groups;
}
public Forest buildForest() {
return FB.build();
}
}

/**
* @author https://atcoder.jp/users/suisen
*/
class Tree {
final int n;
final int root;
final int[] par;
final int[] pre;
final int[] pst;
Tree(int n, int root, int[][] adj) {
this.n = n;
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) {
}
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;
this.cst = new long[n];
for (int u = 0; u < n; u++) {
for (int i = 0; i < k; i++) {
if (v == par[u]) {
cst[u] = c;
} else {
cst[v] = c;
}
}
}
}
public long[] getWeights() {
return cst;
}
public long getWeight(int u, int i) {
}
}

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

class Forest {
final int n;
final int groupNum;
final int[] ids;
final int[] idx;
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[] idx, int[] root) {
this.n = n;
this.groupNum = groups.length;
this.ids = ids;
this.idx = idx;
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[] 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) {
}
public final int parent(int u) {
return par[u];
}
public final int[] parent() {
return par;
}
public final int[] ids() {
return ids;
}
public final int[] indices() {
return idx;
}
public final int id(int u) {
return ids[u];
}
public final int index(int u) {
return idx[u];
}
public final int[] group(int id) {
return groups[id];
}
public final int get(int id, int index) {
return groups[id][index];
}
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), idx[root]);
for (int u : group(id)) {
if (u != root) {
}
}
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) {
time[u] = ++t;
}
public void setRootIfAbsent(int u) {
time[u] = ++t;
}
}
public boolean isConnected(int u, int v) {
}
public int addEdgeIfDisconnected(int u, int v, long cost) {
return -1;
}
public int addEdgeIfDisconnected(int u, int v) {
}
public int addEdge(int u, int v, long cost) {
edges[ptr] = new SimpleEdge(u, v, cost);
count[u]++;
count[v]++;
merge(u, v);
return ptr++;
}
public int addEdge(int u, int v) {
}
public Forest build() {
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;
}
for (int i = 0; i < n; i++) root[i] = root[leader(i)];
int[] idx = new int[n];
int[] ids = new int[n];
int[][] groups = groups(idx, ids);
return new Forest(n, adj, groups, ids, idx, root);
}

public WeightedForest buildWeightedForest() {
long[][] cst = new long[n][];
for (int i = 0; i < n; i++) {
cst[i] = new long[count[i]];
}
for (int i = 0; i < ptr; i++) {
int u = edges[i].from;
int v = edges[i].to;
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[] idx = new int[n];
int[] ids = new int[n];
int[][] groups = groups(idx, ids);
return new WeightedForest(n, adj, groups, ids, idx, root, cst);
}

private void merge(int x, int y) {
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;
}
}
int p = dsu[x];
return p < 0 ? x : (dsu[x] = leader(p));
}
private int[][] groups(int[] idx, 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++) {
groups[ids[i] = j][idx[i] = --cnt[j]] = i;
}
return groups;
}
}

/**
* @verified
* - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
*/
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;
}
}
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;

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

/**
* @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;
}
}

/**
* @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 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));
}

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

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

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

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() {
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() {
}

public final long nextLong() {
long n = 0;
boolean isNegative = false;
int b = skipUnprintableChars();
if (b == '-') {
isNegative = true;
}
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');
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';
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';
}
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;
}
}
}
```

#### Submission Info

Submission Time 2020-11-17 04:39:17+0900 H - Union Sets suisen Java (OpenJDK 11.0.6) 600 35478 Byte AC 511 ms 140544 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
Case Name Status Exec Time Memory
sample_01.txt AC 103 ms 34080 KB
sample_02.txt AC 89 ms 34108 KB
sample_03.txt AC 92 ms 34136 KB
subtask_1_1.txt AC 87 ms 34188 KB
subtask_1_10.txt AC 118 ms 34992 KB
subtask_1_11.txt AC 177 ms 39416 KB
subtask_1_12.txt AC 293 ms 89096 KB
subtask_1_13.txt AC 95 ms 34304 KB
subtask_1_14.txt AC 90 ms 34056 KB
subtask_1_15.txt AC 128 ms 35340 KB
subtask_1_16.txt AC 103 ms 34660 KB
subtask_1_17.txt AC 102 ms 34032 KB
subtask_1_18.txt AC 96 ms 34156 KB
subtask_1_19.txt AC 262 ms 76972 KB
subtask_1_2.txt AC 82 ms 34080 KB
subtask_1_20.txt AC 91 ms 34204 KB
subtask_1_21.txt AC 98 ms 35008 KB
subtask_1_22.txt AC 208 ms 63608 KB
subtask_1_23.txt AC 481 ms 139300 KB
subtask_1_24.txt AC 486 ms 138948 KB
subtask_1_25.txt AC 503 ms 139512 KB
subtask_1_26.txt AC 483 ms 137340 KB
subtask_1_27.txt AC 503 ms 94584 KB
subtask_1_28.txt AC 511 ms 94508 KB
subtask_1_29.txt AC 480 ms 139076 KB
subtask_1_3.txt AC 92 ms 34280 KB
subtask_1_30.txt AC 487 ms 138776 KB
subtask_1_31.txt AC 498 ms 139860 KB
subtask_1_32.txt AC 499 ms 137440 KB
subtask_1_33.txt AC 503 ms 94392 KB
subtask_1_34.txt AC 488 ms 94336 KB
subtask_1_35.txt AC 477 ms 138444 KB
subtask_1_36.txt AC 477 ms 138696 KB
subtask_1_37.txt AC 499 ms 140544 KB
subtask_1_38.txt AC 495 ms 137528 KB
subtask_1_39.txt AC 503 ms 94816 KB
subtask_1_4.txt AC 423 ms 101176 KB
subtask_1_40.txt AC 490 ms 95392 KB
subtask_1_41.txt AC 135 ms 34756 KB
subtask_1_42.txt AC 140 ms 35124 KB
subtask_1_43.txt AC 389 ms 76512 KB
subtask_1_44.txt AC 481 ms 94696 KB
subtask_1_45.txt AC 127 ms 34784 KB
subtask_1_46.txt AC 488 ms 139404 KB
subtask_1_5.txt AC 108 ms 34580 KB
subtask_1_6.txt AC 297 ms 89220 KB
subtask_1_7.txt AC 115 ms 41940 KB
subtask_1_8.txt AC 142 ms 49584 KB
subtask_1_9.txt AC 143 ms 45932 KB