Problem: Only T milliseconds left before the start of well-known online programming contest Codehorses Round 2017.

Polycarp needs to download B++ compiler to take part in the contest. The size of the file is f bytes.

Polycarp's internet tariff allows to download data at the rate of one byte per t0 milliseconds. This tariff is already prepaid, and its use does not incur any expense for Polycarp. In addition, the Internet service provider offers two additional packages:

  * download a1 bytes at the rate of one byte per t1 milliseconds, paying p1 burles for the package; 
  * download a2 bytes at the rate of one byte per t2 milliseconds, paying p2 burles for the package. 



Polycarp can buy any package many times. When buying a package, its price (p1 or p2) is prepaid before usage. Once a package is bought it replaces the regular tariff until package data limit is completely used. After a package is consumed Polycarp can immediately buy a new package or switch to the regular tariff without loosing any time. While a package is in use Polycarp can't buy another package or switch back to the regular internet tariff.

Find the minimum amount of money Polycarp has to spend to download an f bytes file no more than in T milliseconds.

Note that because of technical reasons Polycarp can download only integer number of bytes using regular tariff and both packages. I.e. in each of three downloading modes the number of downloaded bytes will be integer. It means that Polycarp can't download a byte partially using the regular tariff or/and both packages.

Input

The first line contains three integer numbers f, T and t0 (1 ≤ f, T, t0 ≤ 107) — size of the file to download (in bytes), maximal time to download the file (in milliseconds) and number of milliseconds to download one byte using the regular internet tariff.

The second line contains a description of the first additional package. The line contains three integer numbers a1, t1 and p1 (1 ≤ a1, t1, p1 ≤ 107), where a1 is maximal sizes of downloaded data (in bytes), t1 is time to download one byte (in milliseconds), p1 is price of the package (in burles).

The third line contains a description of the second additional package. The line contains three integer numbers a2, t2 and p2 (1 ≤ a2, t2, p2 ≤ 107), where a2 is maximal sizes of downloaded data (in bytes), t2 is time to download one byte (in milliseconds), p2 is price of the package (in burles).

Polycarp can buy any package many times. Once package is bought it replaces the regular tariff until package data limit is completely used. While a package is in use Polycarp can't buy another package or switch back to the regular internet tariff.

Output

Print the minimum amount of money that Polycarp needs to pay to download B++ compiler no more than in T milliseconds. If there is no solution, print the only integer -1.

Examples

Input

120 964 20
26 8 8
13 10 4


Output

40


Input

10 200 20
1 1 1
2 2 3


Output

0


Input

8 81 11
4 10 16
3 10 12


Output

28


Input

8 79 11
4 10 16
3 10 12


Output

-1

Note

In the first example Polycarp has to buy the first additional package 5 times and do not buy the second additional package. He downloads 120 bytes (of total 26·5 = 130 bytes) in 120·8 = 960 milliseconds (960 ≤ 964). He spends 8·5 = 40 burles on it.

In the second example Polycarp has enough time to download 10 bytes. It takes 10·20 = 200 milliseconds which equals to upper constraint on download time.

In the third example Polycarp has to buy one first additional package and one second additional package.

In the fourth example Polycarp has no way to download the file on time.

Solution (in JAVA):

Solution:
import java.awt.*;
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
import java.util.List;
import java.util.Queue;

import static java.lang.Math.max;
import static java.lang.Math.min;


public class C implements Runnable{

    // SOLUTION!!!
    // HACK ME PLEASE IF YOU CAN!!!
    // PLEASE!!!
    // PLEASE!!!
    // PLEASE!!!

    private final static Random rnd = new Random();
    private final static String fileName = "";
    
    private final static long MODULO = 1000 * 1000 * 1000 + 7;

    final int MAX_RND = 10;

    private void solve1() {
        for (int it = 0; it < 10; ++it) {
            int need = rnd.nextInt(10000) + 1;
            long maxTime = rnd.nextInt(10000000) + 1;
            long freeDefaultTime = rnd.nextInt(10) + 1;

            int firstDefaultSize = rnd.nextInt(100) + 1;
            long firstDefaultTime = rnd.nextInt(10) + 1;
            long firstDefaultCost = rnd.nextInt(10) + 1;

            int secondDefaultSize = rnd.nextInt(100) + 1;
            long secondDefaultTime = rnd.nextInt(10) + 1;
            long secondDefaultCost = rnd.nextInt(10) + 1;

            long[] answer = getAnswer(need, maxTime, freeDefaultTime,
                    firstDefaultSize, firstDefaultTime, firstDefaultCost,
                    secondDefaultSize, secondDefaultTime, secondDefaultCost);

            long[] bruteAnswer = getBruteAnswer(need, maxTime, freeDefaultTime,
                    firstDefaultSize, firstDefaultTime, firstDefaultCost,
                    secondDefaultSize, secondDefaultTime, secondDefaultCost);

            if (answer[0] != bruteAnswer[0]) {
                System.err.println("GOTCHA");

                System.err.println(Arrays.toString(answer));
                System.err.println(Arrays.toString(bruteAnswer));
                System.err.println(need + " " + maxTime + " " +firstDefaultTime);
                System.err.println(firstDefaultSize + " " + firstDefaultTime + " " +firstDefaultCost);
                System.err.println(secondDefaultSize + " " + secondDefaultTime + " " +secondDefaultCost);
            }
        }
    }

    private void solve() {
        long need = readInt();
        long maxTime = readInt();
        long freeDefaultTime = readInt();

        long firstDefaultSize = readInt();
        long firstDefaultTime = readInt();
        long firstDefaultCost = readInt();

        long secondDefaultSize = readInt();
        long secondDefaultTime = readInt();
        long secondDefaultCost = readInt();

//        long[] firstTimes = new long[need + 1];
//        long[] firstCosts = new long[need + 1];
//
//        for (int i = 1; i <= need; i += firstDefaultSize) {
//            firstTimes[i] = firstDefaultTime + (i == 1 ? 0 : firstTimes[i - firstDefaultSize]);
//            firstCosts[i] = firstDefaultCost + (i == 1 ? 0 : firstCosts[i - firstDefaultSize]);
//        }
//
//        for (int i = 1; i <= need; ++i) {
//            firstTimes[i] = max(firstTimes[i - 1], firstTimes[i]);
//            firstCosts[i] = max(firstCosts[i - 1], firstCosts[i]);
//        }
//
//        long[] secondTimes = new long[need + 1];
//        long[] secondCosts = new long[need + 1];
//
//        for (int i = 1; i <= need; i += secondDefaultSize) {
//            secondTimes[i] = secondDefaultTime + (i == 1 ? 0 : secondTimes[i - secondDefaultSize]);
//            secondCosts[i] = secondDefaultCost + (i == 1 ? 0 : secondCosts[i - secondDefaultSize]);
//        }
//
//        for (int i = 1; i <= need; ++i) {
//            secondTimes[i] = max(secondTimes[i - 1], secondTimes[i]);
//            secondCosts[i] = max(secondCosts[i - 1], secondCosts[i]);
//        }
//
//        long[] freeTimes = new long[need + 1];
//        for (int i = 1; i <= need; ++i) {
//            freeTimes[i] = freeTimes[i - 1] + freeDefaultTime;
//        }

        long[] answer = getAnswer(need, maxTime, freeDefaultTime,
                firstDefaultSize, firstDefaultTime, firstDefaultCost,
                secondDefaultSize, secondDefaultTime, secondDefaultCost
        );

        out.println(answer[0]);
    }

    long[] getAnswer(long need, long maxTime, long freeDefaultTime,
                     long firstDefaultSize,long firstDefaultTime,long firstDefaultCost,
                     long secondDefaultSize,long secondDefaultTime,long secondDefaultCost) {
        long answer = Long.MAX_VALUE;
        long firstOptimal = 0, secondOptimal = 0;
        
        for (long firstCount = 0, firstSize = 0, firstTime = 0, firstCost = 0; ;
             ++firstCount, firstSize += firstDefaultSize,
            firstCost += firstDefaultCost,
                     firstTime += firstDefaultTime * firstDefaultSize) {

            if (firstSize >= need) {
                firstSize = need;
                firstTime = firstDefaultTime * firstSize;
            }

            long canUseTime = maxTime - firstTime;
            long needUseSize = need - firstSize;
            if (canUseTime >= 0) {
                if (freeDefaultTime <= secondDefaultTime) {
                    long freeTime = freeDefaultTime * needUseSize;
                    if (freeTime + firstTime <= maxTime) {
                        if (answer > firstCost) {
                            answer = firstCost;
                            firstOptimal = firstCount;
                            secondOptimal = 0;
                        }
                    }
                } else {
                    long lowerSideCount = needUseSize / secondDefaultSize;
                    long lowerSecondSize = secondDefaultSize * lowerSideCount;
                    long lowerFreeSize = needUseSize - lowerSecondSize;

                    long lowerSecondTime = lowerSecondSize * secondDefaultTime;
                    long lowerFreeTime = lowerFreeSize * freeDefaultTime;

                    if (lowerSecondTime + lowerFreeTime <= canUseTime) {

                        if (answer > firstCost + lowerSideCount * secondDefaultCost) {
                            answer = firstCost + lowerSideCount * secondDefaultCost;
                            firstOptimal = firstCount;
                            secondOptimal = lowerSideCount;
                        }
                    }

                    long upperSideCount = needUseSize / secondDefaultSize;
                    if (needUseSize % secondDefaultSize != 0) ++upperSideCount;
                    long upperSecondSize = min(needUseSize, secondDefaultSize * upperSideCount);
                    long upperFreeSize = needUseSize - upperSecondSize;

                    long upperSecondTime = upperSecondSize * secondDefaultTime;
                    long upperFreeTime = upperFreeSize * freeDefaultTime;

                    if (upperSecondTime + upperFreeTime <= canUseTime) {
                        if (answer > firstCost + upperSideCount * secondDefaultCost) {
                            answer = firstCost + upperSideCount * secondDefaultCost;
                            firstOptimal = firstCount;
                            secondOptimal = upperSideCount;
                        }

                        long exactNumerator = ((needUseSize * freeDefaultTime - canUseTime));
                        long exactDenominator = (freeDefaultTime - secondDefaultTime) * secondDefaultSize;


                        long exactSideCount = exactNumerator / exactDenominator;
                        if (exactNumerator < 0) exactSideCount = 0;
                        else if (exactNumerator % exactDenominator != 0) {
                            exactSideCount++;
                        }
                        if (exactSideCount >= 0) {
                            long exactSecondSize = min(needUseSize, secondDefaultSize * exactSideCount);
                            long exactFreeSize = needUseSize - exactSecondSize;

                            long exactSecondTime = exactSecondSize * secondDefaultTime;
                            long exactFreeTime = exactFreeSize * freeDefaultTime;

                            if (exactSecondTime + exactFreeTime <= canUseTime) {

                                if (answer > firstCost + exactSideCount * secondDefaultCost) {
                                    answer = firstCost + exactSideCount * secondDefaultCost;
                                    firstOptimal = firstCount;
                                    secondOptimal = exactSideCount;
                                }
                            }
                        }
                    }


                }
            }

            if (firstSize >= need) break;
        }
        
        for (long secondCount = 0, secondSize = 0, secondCost = 0, secondTime = 0; ;
             ++secondCount, secondSize += secondDefaultSize,
                     secondCost += secondDefaultCost,
                     secondTime += secondDefaultTime * secondDefaultSize) {

            if (secondSize >= need) {
                secondSize = need;
                secondTime = secondDefaultTime * secondSize;
            }

            long canUseTime = maxTime - secondTime;
            long needUseSize = need - secondSize;
            if (canUseTime >= 0) {
                if (freeDefaultTime <= firstDefaultTime) {
                    long freeTime = freeDefaultTime * needUseSize;
                    if (freeTime + secondTime <= maxTime) {
                        if (answer > secondCost) {
                            answer = secondCost;
                            secondOptimal = secondCount;
                            firstOptimal = 0;
                        }
                    }
                } else {
                    long lowerSideCount = needUseSize / firstDefaultSize;
                    long lowerfirstSize = firstDefaultSize * lowerSideCount;
                    long lowerFreeSize = needUseSize - lowerfirstSize;

                    long lowerfirstTime = lowerfirstSize * firstDefaultTime;
                    long lowerFreeTime = lowerFreeSize * freeDefaultTime;

                    if (lowerfirstTime + lowerFreeTime <= canUseTime) {

                        if (answer > secondCost + lowerSideCount * firstDefaultCost) {
                            answer = secondCost + lowerSideCount * firstDefaultCost;
                            secondOptimal = secondCount;
                            firstOptimal = lowerSideCount;
                        }
                    }

                    long upperSideCount = needUseSize / firstDefaultSize;
                    if (needUseSize % firstDefaultSize != 0) ++upperSideCount;
                    long upperfirstSize = min(needUseSize, firstDefaultSize * upperSideCount);
                    long upperFreeSize = needUseSize - upperfirstSize;

                    long upperfirstTime = upperfirstSize * firstDefaultTime;
                    long upperFreeTime = upperFreeSize * freeDefaultTime;

                    if (upperfirstTime + upperFreeTime <= canUseTime) {
                        if (answer > secondCost + upperSideCount * firstDefaultCost) {
                            answer = secondCost + upperSideCount * firstDefaultCost;
                            secondOptimal = secondCount;
                            firstOptimal = upperSideCount;
                        }

                        long exactNumerator = ((needUseSize * freeDefaultTime - canUseTime));
                        long exactDenominator = (freeDefaultTime - firstDefaultTime) * firstDefaultSize;


                        long exactSideCount = exactNumerator / exactDenominator;
                        if (exactNumerator < 0) exactSideCount = 0;
                        else if (exactNumerator % exactDenominator != 0) {
                            exactSideCount++;
                        }
                        if (exactSideCount >= 0) {
                            long exactfirstSize = min(needUseSize, firstDefaultSize * exactSideCount);
                            long exactFreeSize = needUseSize - exactfirstSize;

                            long exactfirstTime = exactfirstSize * firstDefaultTime;
                            long exactFreeTime = exactFreeSize * freeDefaultTime;

                            if (exactfirstTime + exactFreeTime <= canUseTime) {

                                if (answer > secondCost + exactSideCount * firstDefaultCost) {
                                    answer = secondCost + exactSideCount * firstDefaultCost;
                                    secondOptimal = secondCount;
                                    firstOptimal = exactSideCount;
                                }
                            }
                        }
                    }


                }
            }

            if (secondSize >= need) break;
        }

        if (answer == Long.MAX_VALUE) {
            answer = -1;
        }

        return new long[] { answer, firstOptimal, secondOptimal };
    }

    long[] getBruteAnswer(int need, long maxTime, long freeDefaultTime,
                        int firstDefaultSize,long firstDefaultTime,long firstDefaultCost,
                        int secondDefaultSize,long secondDefaultTime,long secondDefaultCost) {
        long answer = Long.MAX_VALUE;
        long firstOptimal = 0, secondOptimal = 0;

        for (int firstCount = 0; ; ++firstCount) {
            int firstSize = min(need, firstCount * firstDefaultSize);
            if (firstSize >= need) firstSize = need;

            long firstTime = firstSize * firstDefaultTime;
            long firstCost = firstCount * firstDefaultCost;

            int needUseSize = (need - firstSize);
            for (int secondCount = 0; ; ++secondCount) {
                int secondSize = min(needUseSize, secondCount * secondDefaultSize);
                if (secondSize >= needUseSize) secondSize = needUseSize;

                long secondTime = secondSize * secondDefaultTime;
                long secondCost = secondCount * secondDefaultCost;

                int freeSize = needUseSize - secondSize;
                long freeTime = freeSize * freeDefaultTime;

                if (firstTime + secondTime + freeTime <= maxTime) {
                    if (answer > firstCost + secondCost) {
                        answer = firstCost + secondCost;
                        firstOptimal = firstCount;
                        secondOptimal = secondCount;
                    }
                }

                if (secondSize >= needUseSize) break;
            }

            if (firstSize >= need) break;
        }

        if (answer == Long.MAX_VALUE) {
            answer = -1;
        }

        return new long[] { answer, firstOptimal, secondOptimal };
    }

    /////////////////////////////////////////////////////////////////////

    private static long add(long a, long b) { return (a + b) % MODULO; }
    private static long subtract(long a, long b) { return add(a, MODULO - b) % MODULO; }
    private static long mult(long a, long b) { return (a * b) % MODULO; }

    /////////////////////////////////////////////////////////////////////

    private final static boolean FIRST_INPUT_STRING = false;
    private final static boolean MULTIPLE_TESTS = false;
    private final boolean ONLINE_JUDGE = !new File("input.txt").exists();
//    private final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    private final static int MAX_STACK_SIZE = 128;

    private final static boolean OPTIMIZE_READ_NUMBERS = false;

    /////////////////////////////////////////////////////////////////////

    public void run(){
        try{
            timeInit();
            Locale.setDefault(Locale.US);

            init();

            if (ONLINE_JUDGE) {
                solve();
            } else {
                do {
                    try {
                        timeInit();
                        solve();
                        time();

                        out.println();
                    } catch (NumberFormatException e) {
                        break;
                    } catch (NullPointerException e) {
                        if (FIRST_INPUT_STRING) break;
                        else throw e;
                    }
                } while (MULTIPLE_TESTS);
            }

            out.close();
            time();
        }catch (Exception e){
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    /////////////////////////////////////////////////////////////////////

    private BufferedReader in;
    private OutputWriter out;
    private StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args){
        new Thread(null, new C(), "", MAX_STACK_SIZE * (1L << 20)).start();
    }

    /////////////////////////////////////////////////////////////////////

    private void init() throws FileNotFoundException{
        Locale.setDefault(Locale.US);

        if (ONLINE_JUDGE){
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new OutputWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new OutputWriter(fileName + ".out");
            }
        }else{
            in = new BufferedReader(new FileReader("input.txt"));
            out = new OutputWriter("output.txt");
        }
    }

    ////////////////////////////////////////////////////////////////

    private long timeBegin;

    private void timeInit() {
        this.timeBegin = System.currentTimeMillis();
    }

    private void time(){
        long timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    private void debug(Object... objects){
        if (ONLINE_JUDGE){
            for (Object o: objects){
                System.err.println(o.toString());
            }
        }
    }

    /////////////////////////////////////////////////////////////////////

    private String delim = " ";

    private String readLine() {
        try {
            return in.readLine();
        } catch (IOException e) {
            throw new RuntimeIOException(e);
        }
    }

    private String readString() {
        try {
            while(!tok.hasMoreTokens()){
                tok = new StringTokenizer(readLine(), delim);
            }

            return tok.nextToken(delim);
        } catch (NullPointerException e) {
            return null;
        }
    }

    /////////////////////////////////////////////////////////////////

    private final char NOT_A_SYMBOL = '\0';

    private char readChar() {
        try {
            int intValue = in.read();

            if (intValue == -1){
                return NOT_A_SYMBOL;
            }

            return (char) intValue;
        } catch (IOException e) {
            throw new RuntimeIOException(e);
        }
    }

    private char[] readCharArray() {
        return readLine().toCharArray();
    }

    private char[][] readCharField(int rowsCount) {
        char[][] field = new char[rowsCount][];
        for (int row = 0; row < rowsCount; ++row) {
            field[row] = readCharArray();
        }

        return field;
    }

    /////////////////////////////////////////////////////////////////

    private long optimizedReadLong() {
        int sign = 1;
        long result = 0;
        boolean started = false;
        while (true) {
            try {
                int j = in.read();
                if (-1 == j) {
                    if (started) return sign * result;
                    throw new NumberFormatException();
                }

                if (j == '-') {
                    if (started) throw new NumberFormatException();
                    sign = -sign;
                }

                if ('0' <= j && j <= '9') {
                    result = result * 10 + j - '0';
                    started = true;
                } else if (started) {
                    return sign * result;
                }
            } catch (IOException e) {
                throw new RuntimeIOException(e);
            }
        }
    }

    private int readInt() {

        if (!OPTIMIZE_READ_NUMBERS) {
            return Integer.parseInt(readString());
        } else {
            return (int) optimizedReadLong();
        }
    }

    private int[] readIntArray(int size) {
        int[] array = new int[size];

        for (int index = 0; index < size; ++index){
            array[index] = readInt();
        }

        return array;
    }

    private int[] readSortedIntArray(int size) {
        Integer[] array = new Integer[size];

        for (int index = 0; index < size; ++index) {
            array[index] = readInt();
        }
        Arrays.sort(array);

        int[] sortedArray = new int[size];
        for (int index = 0; index < size; ++index) {
            sortedArray[index] = array[index];
        }

        return sortedArray;
    }

    private int[] readIntArrayWithDecrease(int size) {
        int[] array = readIntArray(size);

        for (int i = 0; i < size; ++i) {
            array[i]--;
        }

        return array;
    }

    ///////////////////////////////////////////////////////////////////

    private int[][] readIntMatrix(int rowsCount, int columnsCount) {
        int[][] matrix = new int[rowsCount][];

        for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) {
            matrix[rowIndex] = readIntArray(columnsCount);
        }

        return matrix;
    }

    private int[][] readIntMatrixWithDecrease(int rowsCount, int columnsCount) {
        int[][] matrix = new int[rowsCount][];

        for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) {
            matrix[rowIndex] = readIntArrayWithDecrease(columnsCount);
        }

        return matrix;
    }

    ///////////////////////////////////////////////////////////////////

    private long readLong() {
        if (!OPTIMIZE_READ_NUMBERS) {
            return Long.parseLong(readString());
        } else {
            return optimizedReadLong();
        }
    }

    private long[] readLongArray(int size) {
        long[] array = new long[size];

        for (int index = 0; index < size; ++index){
            array[index] = readLong();
        }

        return array;
    }

    ////////////////////////////////////////////////////////////////////

    private double readDouble() {
        return Double.parseDouble(readString());
    }

    private double[] readDoubleArray(int size) {
        double[] array = new double[size];

        for (int index = 0; index < size; ++index){
            array[index] = readDouble();
        }

        return array;
    }

    ////////////////////////////////////////////////////////////////////

    private BigInteger readBigInteger() {
        return new BigInteger(readString());
    }

    private BigDecimal readBigDecimal() {
        return new BigDecimal(readString());
    }

    /////////////////////////////////////////////////////////////////////

    private Point readPoint() {
        int x = readInt();
        int y = readInt();
        return new Point(x, y);
    }

    private Point[] readPointArray(int size) {
        Point[] array = new Point[size];

        for (int index = 0; index < size; ++index){
            array[index] = readPoint();
        }

        return array;
    }

    /////////////////////////////////////////////////////////////////////

    @Deprecated
    private List<Integer>[] readGraph(int vertexNumber, int edgeNumber) {
        @SuppressWarnings("unchecked")
        List<Integer>[] graph = new List[vertexNumber];

        for (int index = 0; index < vertexNumber; ++index){
            graph[index] = new ArrayList<Integer>();
        }

        while (edgeNumber-- > 0){
            int from = readInt() - 1;
            int to = readInt() - 1;

            graph[from].add(to);
            graph[to].add(from);
        }

        return graph;
    }

    private static class GraphBuilder {

        final int size;
        final List<Integer>[] edges;

        static GraphBuilder createInstance(int size) {
            List<Integer>[] edges = new List[size];
            for (int v = 0; v < size; ++v) {
                edges[v] = new ArrayList<Integer>();
            }

            return new GraphBuilder(edges);
        }

        private GraphBuilder(List<Integer>[] edges) {
            this.size = edges.length;
            this.edges = edges;
        }

        public void addEdge(int from, int to) {
            addDirectedEdge(from, to);
            addDirectedEdge(to, from);
        }

        public void addDirectedEdge(int from, int to) {
            edges[from].add(to);
        }

        public int[][] build() {
            int[][] graph = new int[size][];
            for (int v = 0; v < size; ++v) {
                List<Integer> vEdges = edges[v];
                graph[v] = castInt(vEdges);
            }

            return graph;
        }
    }

    private final static int ZERO_INDEXATION = 0, ONE_INDEXATION = 1;

    private int[][] readUnweightedGraph(int vertexNumber, int edgesNumber) {
        return readUnweightedGraph(vertexNumber, edgesNumber, ONE_INDEXATION, false);
    }

    private int[][] readUnweightedGraph(int vertexNumber, int edgesNumber,
                                        int indexation, boolean directed
    ) {
        GraphBuilder graphBuilder = GraphBuilder.createInstance(vertexNumber);
        for (int i = 0; i < edgesNumber; ++i) {
            int from = readInt() - indexation;
            int to = readInt() - indexation;

            if (directed) graphBuilder.addDirectedEdge(from, to);
            else graphBuilder.addEdge(from, to);
        }

        return graphBuilder.build();
    }

    private static class Edge {
        int to;
        int w;

        Edge(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }

    private Edge[][] readWeightedGraph(int vertexNumber, int edgesNumber) {
        return readWeightedGraph(vertexNumber, edgesNumber, ONE_INDEXATION, false);
    }

    private Edge[][] readWeightedGraph(int vertexNumber, int edgesNumber,
                                       int indexation, boolean directed) {
        @SuppressWarnings("unchecked")
        List<Edge>[] graph = new List[vertexNumber];
        for (int v = 0; v < vertexNumber; ++v) {
            graph[v] = new ArrayList<Edge>();
        }

        while (edgesNumber --> 0) {
            int from = readInt() - indexation;
            int to = readInt() - indexation;
            int w = readInt();

            graph[from].add(new Edge(to, w));
            if (!directed) graph[to].add(new Edge(from, w));
        }

        Edge[][] graphArrays = new Edge[vertexNumber][];
        for (int v = 0; v < vertexNumber; ++v) {
            graphArrays[v] = graph[v].toArray(new Edge[0]);
        }

        return graphArrays;
    }

    /////////////////////////////////////////////////////////////////////

    private static class IntIndexPair {

        static Comparator<IntIndexPair> increaseComparator = new Comparator<C.IntIndexPair>() {

            @Override
            public int compare(C.IntIndexPair indexPair1, C.IntIndexPair indexPair2) {
                int value1 = indexPair1.value;
                int value2 = indexPair2.value;

                if (value1 != value2) return value1 - value2;

                int index1 = indexPair1.index;
                int index2 = indexPair2.index;

                return index1 - index2;
            }
        };

        static Comparator<IntIndexPair> decreaseComparator = new Comparator<C.IntIndexPair>() {

            @Override
            public int compare(C.IntIndexPair indexPair1, C.IntIndexPair indexPair2) {
                int value1 = indexPair1.value;
                int value2 = indexPair2.value;

                if (value1 != value2) return -(value1 - value2);

                int index1 = indexPair1.index;
                int index2 = indexPair2.index;

                return index1 - index2;
            }
        };

        static IntIndexPair[] from(int[] array) {
            IntIndexPair[] iip = new IntIndexPair[array.length];
            for (int i = 0; i < array.length; ++i) {
                iip[i] = new IntIndexPair(array[i], i);
            }

            return iip;
        }

        int value, index;

        IntIndexPair(int value, int index) {
            super();
            this.value = value;
            this.index = index;
        }

        int getRealIndex() {
            return index + 1;
        }
    }

    private IntIndexPair[] readIntIndexArray(int size) {
        IntIndexPair[] array = new IntIndexPair[size];

        for (int index = 0; index < size; ++index) {
            array[index] = new IntIndexPair(readInt(), index);
        }

        return array;
    }

    /////////////////////////////////////////////////////////////////////

    private static class OutputWriter extends PrintWriter {

        final int DEFAULT_PRECISION = 12;

        private int precision;
        private String format, formatWithSpace;

        {
            precision = DEFAULT_PRECISION;

            format = createFormat(precision);
            formatWithSpace = format + " ";
        }

        OutputWriter(OutputStream out) {
            super(out);
        }

        OutputWriter(String fileName) throws FileNotFoundException {
            super(fileName);
        }

        int getPrecision() {
            return precision;
        }

        void setPrecision(int precision) {
            precision = max(0, precision);
            this.precision = precision;

            format = createFormat(precision);
            formatWithSpace = format + " ";
        }

        String createFormat(int precision){
            return "%." + precision + "f";
        }

        @Override
        public void print(double d){
            printf(format, d);
        }
        
        @Override
        public void println(double d){
            print(d);
            println();
        }

        void printWithSpace(double d){
            printf(formatWithSpace, d);
        }

        void printAll(double...d){
            for (int i = 0; i < d.length - 1; ++i){
                printWithSpace(d[i]);
            }

            print(d[d.length - 1]);
        }

        void printlnAll(double... d){
            printAll(d);
            println();
        }
        
        void printAll(int... array) {
        	for (int value : array) {
        		print(value + " ");
        	}
        }
        
        void printlnAll(int... array) {
        	printAll(array);
        	println();
        }
        
        void printAll(long... array) {
        	for (long value : array) {
        		print(value + " ");
        	}
        }
        
        void printlnAll(long... array) {
        	printAll(array);
        	println();
        }
    }

    /////////////////////////////////////////////////////////////////////

    private static class RuntimeIOException extends RuntimeException {

        /**
         *
         */
        private static final long serialVersionUID = -6463830523020118289L;

        RuntimeIOException(Throwable cause) {
            super(cause);
        }
    }

    /////////////////////////////////////////////////////////////////////
    //////////////// Some useful constants andTo functions ////////////////
    /////////////////////////////////////////////////////////////////////

    private static final int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final int[][] steps8 = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1},
            {-1, -1}, {1, 1}, {1, -1}, {-1, 1}
    };

    private static boolean checkCell(int row, int rowsCount, int column, int columnsCount) {
        return checkIndex(row, rowsCount) && checkIndex(column, columnsCount);
    }

    private static boolean checkIndex(int index, int lim){
        return (0 <= index && index < lim);
    }

    /////////////////////////////////////////////////////////////////////

    private static int getBit(long mask, int bit) { return (int)((mask >> bit) & 1); }
    private static boolean checkBit(long mask, int bit){
        return getBit(mask, bit) != 0;
    }

    /////////////////////////////////////////////////////////////////////

    private static long getSum(int[] array) {
        long sum = 0;
        for (int value: array) {
            sum += value;
        }

        return sum;
    }

    private static Point getMinMax(int[] array) {
        int min = array[0];
        int max = array[0];

        for (int index = 0, size = array.length; index < size; ++index, ++index) {
            int value = array[index];

            if (index == size - 1) {
                min = min(min, value);
                max = max(max, value);
            } else {
                int otherValue = array[index + 1];

                if (value <= otherValue) {
                    min = min(min, value);
                    max = max(max, otherValue);
                } else {
                    min = min(min, otherValue);
                    max = max(max, value);
                }
            }
        }

        return new Point(min, max);
    }

    /////////////////////////////////////////////////////////////////////

    private static int[] getPrimes(int n) {
        boolean[] used = new boolean[n];
        used[0] = used[1] = true;

        int size = 0;
        for (int i = 2; i < n; ++i) {
            if (!used[i]) {
                ++size;
                for (int j = 2 * i; j < n; j += i) {
                    used[j] = true;
                }
            }
        }

        int[] primes = new int[size];
        for (int i = 0, cur = 0; i < n; ++i) {
            if (!used[i]) {
                primes[cur++] = i;
            }
        }

        return primes;
    }

    /////////////////////////////////////////////////////////////////////

    int[] getDivisors(int value) {
        List<Integer> divisors = new ArrayList<Integer>();
        for (int divisor = 1; divisor * divisor <= value; ++divisor) {
            if (value % divisor == 0) {
                divisors.add(divisor);
                if (divisor * divisor != value) {
                    divisors.add(value / divisor);
                }
            }
        }

        return castInt(divisors);
    }

    /////////////////////////////////////////////////////////////////////

    private static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    private static long gcd(long a, long b) {
        return (a == 0 ? b : gcd(b % a, a));
    }

/////////////////////////////////////////////////////////////////////

    private interface MultiSet<ValueType> {

        int size();

        void inc(ValueType value);
        boolean dec(ValueType value);

        int count(ValueType value);
    }

    private static abstract class MultiSetImpl
            <ValueType, MapType extends Map<ValueType, Integer>>
            implements MultiSet<ValueType> {

        protected final MapType map;
        protected int size;

        protected MultiSetImpl(MapType map) {
            this.map = map;
            this.size = 0;
        }

        public int size() {
            return size;
        }

        public void inc(ValueType value) {
            int count = count(value);
            map.put(value, count + 1);

            ++size;
        }

        public boolean dec(ValueType value) {
            int count = count(value);
            if (count == 0) return false;

            if (count == 1) map.remove(value);
            else map.put(value, count - 1);

            --size;
            return true;
        }

        public int count(ValueType value) {
            Integer count = map.get(value);
            return (count == null ? 0 : count);
        }
    }

    private static class HashMultiSet<ValueType>
            extends MultiSetImpl<ValueType, Map<ValueType, Integer>> {

        public static <ValueType> MultiSet<ValueType> createMultiSet() {
            Map<ValueType, Integer> map = new HashMap<ValueType, Integer>();
            return new HashMultiSet<ValueType>(map);
        }

        HashMultiSet(Map<ValueType, Integer> map) {
            super(map);
        }
    }

    /////////////////////////////////////////////////////////////////////

    private interface SortedMultiSet<ValueType> extends MultiSet<ValueType> {

        ValueType min();
        ValueType max();

        ValueType pollMin();
        ValueType pollMax();

        ValueType lower(ValueType value);
        ValueType floor(ValueType value);

        ValueType ceiling(ValueType value);
        ValueType higher(ValueType value);
    }

    private static abstract class SortedMultiSetImpl<ValueType>
            extends MultiSetImpl<ValueType, NavigableMap<ValueType, Integer>>
            implements SortedMultiSet<ValueType> {

        SortedMultiSetImpl(NavigableMap<ValueType, Integer> map) {
            super(map);
        }

        @Override
        public ValueType min() {
            return (size == 0 ? null : map.firstKey());
        }

        @Override
        public ValueType max() {
            return (size == 0 ? null : map.lastKey());
        }

        @Override
        public ValueType pollMin() {
            ValueType first = min();
            if (first != null) dec(first);
            return first;
        }

        @Override
        public ValueType pollMax() {
            ValueType last = max();
            dec(last);
            return last;
        }

        @Override
        public ValueType lower(ValueType value) {
            return map.lowerKey(value);
        }

        @Override
        public ValueType floor(ValueType value) {
            return map.floorKey(value);
        }

        @Override
        public ValueType ceiling(ValueType value) {
            return map.ceilingKey(value);
        }

        @Override
        public ValueType higher(ValueType value) {
            return map.higherKey(value);
        }
    }

    private static class TreeMultiSet<ValueType>
            extends SortedMultiSetImpl<ValueType> {

        public static <ValueType> SortedMultiSet<ValueType> createMultiSet() {
            NavigableMap<ValueType, Integer> map = new TreeMap<ValueType, Integer>();
            return new TreeMultiSet<ValueType>(map);
        }

        TreeMultiSet(NavigableMap<ValueType, Integer> map) {
            super(map);
        }
    }

    /////////////////////////////////////////////////////////////////////

    private static class IdMap<KeyType> extends HashMap<KeyType, Integer> {

        /**
         *
         */
        private static final long serialVersionUID = -3793737771950984481L;

        public IdMap() {
            super();
        }

        int register(KeyType key) {
            Integer id = super.get(key);
            if (id == null) {
                super.put(key, id = size());
            }

            return id;
        }

        int getId(KeyType key) {
            return get(key);
        }
    }

    /////////////////////////////////////////////////////////////////////

    private static class SortedIdMapper<ValueType extends Comparable<ValueType>> {

        private List<ValueType> values;

        public SortedIdMapper() {
            this.values = new ArrayList<ValueType>();
        }

        void addValue(ValueType value) {
            values.add(value);
        }

        IdMap<ValueType> build() {
            Collections.sort(values);

            IdMap<ValueType> ids = new IdMap<ValueType>();
            List<ValueType> uniqueValues = new ArrayList<ValueType>();

            for (int index = 0; index < values.size(); ++index) {
                ValueType value = values.get(index);
                if (index == 0 || values.get(index - 1).compareTo(value) != 0) {
                    ids.register(value);
                    uniqueValues.add(value);
                }
            }
            
            values = uniqueValues;

            return ids;
        }
    }

    /////////////////////////////////////////////////////////////////////

    private static int[] castInt(List<Integer> list) {
        int[] array = new int[list.size()];
        for (int i = 0; i < array.length; ++i) {
            array[i] = list.get(i);
        }

        return array;
    }

    private static long[] castLong(List<Long> list) {
        long[] array = new long[list.size()];
        for (int i = 0; i < array.length; ++i) {
            array[i] = list.get(i);
        }

        return array;
    }

    /////////////////////////////////////////////////////////////////////

    /**
     * Generates list with keys 0..<n
     * @param n - exclusive limit of sequence
     */
    private static List<Integer> order(int n) {
        List<Integer> sequence = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            sequence.add(i);
        }

        return sequence;
    }

    /////////////////////////////////////////////////////////////////////

    interface Rmq {
        int getMin(int left, int right);
        int getMinIndex(int left, int right);
    }

    private static class SparseTable implements Rmq {

        private static final int MAX_BIT = 17;

        int n;
        int[] array;

        SparseTable(int[] array) {
            this.n = array.length;
            this.array = array;
        }

        int[] lengthMaxBits;
        int[][] table;

        int getIndexOfLess(int leftIndex, int rightIndex) {
            return (array[leftIndex] <= array[rightIndex])
                    ? leftIndex
                    : rightIndex;
        }

        SparseTable build() {
            this.lengthMaxBits = new int[n + 1];
            lengthMaxBits[0] = 0;
            for (int i = 1; i <= n; ++i) {
                lengthMaxBits[i] = lengthMaxBits[i - 1];
                int length = (1 << lengthMaxBits[i]);
                if (length + length <= i) ++lengthMaxBits[i];
            }

            this.table = new int[MAX_BIT][n];
            table[0] = castInt(order(n));

            for (int bit = 0; bit < MAX_BIT - 1; ++bit) {
                for (int i = 0, j = (1 << bit); j < n; ++i, ++j) {
                    table[bit + 1][i] = getIndexOfLess(
                            table[bit][i], table[bit][j]
                    );
                }
            }

            return this;
        }

        @Override
        public int getMinIndex(int left, int right) {
            int length = (right - left + 1);

            int bit = lengthMaxBits[length];
            int segmentLength = (1 << bit);

            return getIndexOfLess(
                    table[bit][left], table[bit][right - segmentLength + 1]
            );
        }

        @Override
        public int getMin(int left, int right) {
            return array[getMinIndex(left, right)];
        }
    }

    private static Rmq createRmq(int[] array) {
        return new SparseTable(array).build();
    }

    /////////////////////////////////////////////////////////////////////

    interface Lca {
        Lca build(int root);
        int lca(int a, int b);

        int height(int v);
    }

    private static class LcaRmq implements Lca {

        int n;
        int[][] graph;

        LcaRmq(int[][] graph) {
            this.n = graph.length;
            this.graph = graph;
        }

        int time;

        int[] order;
        int[] heights;
        int[] first;

        Rmq rmq;

        @Override
        public LcaRmq build(int root) {
            this.order = new int[n + n];
            this.heights = new int[n];

            this.first = new int[n];
            Arrays.fill(first, -1);

            this.time = 0;
            dfs(root, 0);

            int[] orderedHeights = new int[n + n];
            for (int i = 0; i < order.length; ++i) {
                orderedHeights[i] = heights[order[i]];
            }

            this.rmq = createRmq(orderedHeights);
            return this;
        }

        void dfs(int from, int height) {
            first[from] = time;
            order[time] = from;
            heights[from] = height;
            ++time;

            for (int to : graph[from]) {
                if (first[to] == -1) {
                    dfs(to, height + 1);

                    order[time] = from;
                    ++time;
                }
            }
        }

        @Override
        public int lca(int a, int b) {
            int aFirst = first[a], bFirst = first[b];
            int left = min(aFirst, bFirst), right = max(aFirst, bFirst);

            int orderIndex = rmq.getMinIndex(left, right);
            return order[orderIndex];
        }

        @Override
        public int height(int v) {
            return heights[v];
        }
    }

    private static class LcaBinary implements Lca {

        private static final int MAX_BIT = 20;

        int n;
        int[][] graph;

        int[] h;
        int[][] parents;

        LcaBinary(int[][] graph) {
            this.n = graph.length;
            this.graph = graph;
        }

        @Override
        public Lca build(int root) {
            this.h = new int[n];

            this.parents = new int[MAX_BIT][n];
            Arrays.fill(parents[0], -1);

            Queue<Integer> queue = new ArrayDeque<Integer>();

            queue.add(root);
            add(root, root);

            while (queue.size() > 0) {
                int from = queue.poll();
                for (int to : graph[from]) {
                    if (parents[0][to] == -1) {
                        add(from, to);
                        queue.add(to);
                    }
                }
            }

            return this;
        }

        void add(int parent, int v) {
            h[v] = h[parent] + 1;
            parents[0][v] = parent;
            for (int bit = 0; bit < MAX_BIT - 1; ++bit) {
                parents[bit + 1][v] = parents[bit][parents[bit][v]];
            }
        }

        @Override
        public int lca(int a, int b) {
            if (h[a] < h[b]) {
                int tmp = a;
                a = b;
                b = tmp;
            }

            int delta = h[a] - h[b];
            for (int bit = MAX_BIT - 1; bit >= 0; --bit) {
                if (delta >= (1 << bit)) {
                    delta -= (1 << bit);
                    a = parents[bit][a];
                }
            }

            if (a == b) return a;

            for (int bit = MAX_BIT - 1; bit >= 0; --bit) {
                int nextA = parents[bit][a], nextB = parents[bit][b];
                if (nextA != nextB) {
                    a = nextA;
                    b = nextB;
                }
            }

            return parents[0][a];
        }

        @Override
        public int height(int v) {
            return h[v];
        }
    }

    private static Lca createLca(int[][] graph, int root) {
        return new LcaRmq(graph).build(root);
    }

    /////////////////////////////////////////////////////////////////////

    private static class BiconnectedGraph {

        int n;
        int[][] graph;

        BiconnectedGraph(int[][] graph) {
            this.n = graph.length;
            this.graph = graph;
        }

        int time;
        int[] tin, up;

        boolean[] used;

        BiconnectedGraph build() {
            calculateTimes();
            condensateComponents();

            return this;
        }

        void calculateTimes() {
            this.tin = new int[n];
            this.up = new int[n];

            this.time = 0;

            this.used = new boolean[n];
            timeDfs(0, -1);
        }

        void timeDfs(int from, int parent) {
            used[from] = true;

            up[from] = tin[from] = time;
            ++time;

            for (int to : graph[from]) {
                if (to == parent) continue;

                if (used[to]) {
                    up[from] = min(up[from], tin[to]);
                } else {
                    timeDfs(to, from);
                    up[from] = min(up[from], up[to]);
                }
            }
        }

        int[] components;
        int[][] componentsGraph;

        int component(int v) { return components[v]; }

        int[][] toGraph() {
            return componentsGraph;
        }

        void condensateComponents() {
            this.components = new int[n];
            Arrays.fill(components, -1);

            for (int v = 0; v < n; ++v) {
                if (components[v] == -1) {
                    componentsDfs(v, v);
                }
            }

            GraphBuilder graphBuilder = GraphBuilder.createInstance(n);

            Set<Point> edges = new HashSet<Point>();
            for (int from = 0; from < n; ++from) {
                int fromComponent = components[from];

                for (int to : graph[from]) {
                    int toComponent = components[to];
                    if (fromComponent == toComponent) continue;

                    Point edge = new Point(fromComponent, toComponent);
                    if (edges.add(edge)) graphBuilder.addDirectedEdge(fromComponent, toComponent);
                }
            }

            this.componentsGraph = graphBuilder.build();
        }

        void componentsDfs(int from, int color) {
            components[from] = color;
            for (int to : graph[from]) {
                if (components[to] != -1) continue;

                if (tin[from] >= up[to] && tin[to] >= up[from]) {
                    componentsDfs(to, color);
                }
            }
        }
    }

    /////////////////////////////////////////////////////////////////////

    private static class VertexBiconnectedGraph {

        static class Edge {
            int to;
            int index;

            Edge(int to, int index) {
                this.to = to;
                this.index = index;
            }
        }

        int n, m;
        List<Edge>[] graph;
        List<Edge> edges;

        VertexBiconnectedGraph(int n) {
            this.n = n;
            this.m = 0;

            this.graph = new List[n];
            for (int v = 0; v < n; ++v) {
                graph[v] = new ArrayList<Edge>();
            }

            this.edges = new ArrayList<Edge>();
        }

        void addEdge(int from, int to) {
            Edge fromToEdge = new Edge(to, m);
            Edge toFromEdge = new Edge(from, m + 1);

            edges.add(fromToEdge);
            edges.add(toFromEdge);

            graph[from].add(fromToEdge);
            graph[to].add(toFromEdge);

            m += 2;
        }

        int time;

        boolean[] used;
        int[] tin, up;
        int[] parents;

        boolean[] isArticulation;

        boolean[] findArticulationPoints() {
            this.isArticulation = new boolean[n];

            this.used = new boolean[n];
            this.parents = new int[n];
            Arrays.fill(parents, -1);

            this.tin = new int[n];
            this.up = new int[n];

            this.time = 0;

            for (int v = 0; v < n; ++v) {
                if (!used[v]) {
                    articulationDfs(v, -1);
                }
            }

            return isArticulation;
        }

        void articulationDfs(int from, int parent) {
            used[from] = true;
            parents[from] = parent;

            ++time;
            up[from] = tin[from] = time;

            int childrenCount = 0;

            for (Edge e : graph[from]) {
                int to = e.to;

                if (to == parent) continue;

                if (used[to]) {
                    up[from] = min(up[from], tin[to]);
                } else {
                    ++childrenCount;

                    articulationDfs(to, from);
                    up[from] = min(up[from], up[to]);
                    if (up[to] >= tin[from] && parent != -1) {
                        isArticulation[from] = true;
                    }
                }
            }

            if (parent == -1 && childrenCount > 1) {
                isArticulation[from] = true;
            }
        }

        int[] edgeColors;
        int maxEdgeColor;

        int[] paintEdges() {
            this.edgeColors = new int[m];
            Arrays.fill(edgeColors, -1);

            this.maxEdgeColor = -1;

            this.used = new boolean[n];

            for (int v = 0; v < n; ++v) {
                if (!used[v]) {
                    ++maxEdgeColor;
                    paintDfs(v, maxEdgeColor, -1);
                }
            }

            return edgeColors;
        }

        void paintEdge(int edgeIndex, int color) {
            if (edgeColors[edgeIndex] != -1) return;

            edgeColors[edgeIndex] = edgeColors[edgeIndex ^ 1] = color;
        }

        void paintDfs(int from, int color, int parent) {
            used[from] = true;

            for (Edge e : graph[from]) {
                int to = e.to;
                if (to == parent) continue;

                if (!used[to]) {
                    if (up[to] >= tin[from]) {
                        int newColor = ++maxEdgeColor;
                        paintEdge(e.index, newColor);
                        paintDfs(to, newColor, from);
                    } else {
                        paintEdge(e.index, color);
                        paintDfs(to, color, from);
                    }
                } else if (up[to] <= tin[from]){
                    paintEdge(e.index, color);
                }
            }
        }

        Set<Integer>[] collectVertexEdgeColors() {
            Set<Integer>[] vertexEdgeColors = new Set[n];
            for (int v = 0; v < n; ++v) {
                vertexEdgeColors[v] = new HashSet<Integer>();
                for (Edge e : graph[v]) {
                    vertexEdgeColors[v].add(edgeColors[e.index]);
                }
            }

            return vertexEdgeColors;
        }

        VertexBiconnectedGraph build() {
            findArticulationPoints();
            paintEdges();
            createComponentsGraph();

            return this;
        }

        int[][] componentsGraph;

        void createComponentsGraph() {
            Set<Integer>[] vertexEdgeColors = collectVertexEdgeColors();

            int edgeColorShift = vertexEdgeColors.length;
            int size = vertexEdgeColors.length + maxEdgeColor + 1;

            GraphBuilder graphBuilder = GraphBuilder.createInstance(size);
            for (int v = 0; v < vertexEdgeColors.length; ++v) {
                for (int edgeColor : vertexEdgeColors[v]) {
                    graphBuilder.addEdge(v, edgeColor + edgeColorShift);
                }
            }

            this.componentsGraph = graphBuilder.build();
        }

        int[][] toGraph() {
            return componentsGraph;
        }
    }

    /////////////////////////////////////////////////////////////////////

    private static class DSU {

        int[] sizes;

        int[] ranks;
        int[] parents;

        static DSU createInstance(int size) {
            int[] sizes = new int[size];
            Arrays.fill(sizes, 1);

            return new DSU(sizes);
        }

        DSU(int[] sizes) {
            this.sizes = sizes;

            int size = sizes.length;

            this.ranks = new int[size];
            Arrays.fill(ranks, 1);

            this.parents = castInt(order(size));
        }

        int get(int v) {
            if (v == parents[v]) return v;
            return parents[v] = get(parents[v]);
        }

        boolean union(int a, int b) {
            a = get(a);
            b = get(b);

            if (a == b) return false;

            if (ranks[a] < ranks[b]) {
                int tmp = a;
                a = b;
                b = tmp;
            }

            parents[b] = a;
            sizes[a] += sizes[b];

            if (ranks[a] == ranks[b]) ++ranks[a];

            return true;
        }
    }

    /////////////////////////////////////////////////////////////////////
}