import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;
import java.util.TreeSet;
import java.util.function.IntPredicate;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.LongPredicate;
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();
        int a = sc.nextInt() - 1;
        int b = sc.nextInt();
        TreeSet<IntPair3> set = new TreeSet<>((p1, p2) -> {
            if (p1.fst == p2.fst) {
                if (p1.snd == p2.snd) {
                    return p1.trd - p2.trd;
                } else {
                    return p1.snd - p2.snd;
                }
            } else {
                return p1.fst - p2.fst;
            }
        });
        for (int i = 0; i < m; i++) {
            set.add(new IntPair3(sc.nextInt() - 1, sc.nextInt(), 1));
        }
        ArrayList<IntPair3> lst = new ArrayList<>();
        while (set.size() >= 2) {
            var p1 = set.first();
            var p2 = set.higher(p1);
            if (p1.fst != p2.fst) {
                set.remove(p1);
                lst.add(p1);
            } else {
                if (p1.snd == p2.snd) {
                    set.remove(p2);
                } else {
                    set.remove(p2);
                    p2.fst = p1.snd;
                    p2.trd += p1.trd;
                    set.add(p2);
                }
            }
        }
        if (set.size() == 1) {
            lst.add(set.first());
        }
        int siz = lst.size();
        IntPair3[] p = lst.toArray(IntPair3[]::new);
        int[] next = new int[siz + 1];
        next[siz] = siz;
        Arrays.fill(next, siz);
        for (int i = 0; i < siz; i++) {
            int l = i, r = siz;
            while (r - l > 1) {
                int md = (l + r) >> 1;
                if (p[md].fst == p[i].snd) {
                    next[i] = md;
                    break;
                } else if (p[md].fst < p[i].snd) {
                    l = md;
                } else {
                    r = md;
                }
            }
        }
        int min = Const.IINF;
        Doubling d = new Doubling(next, siz);
        TreeBuilder tb = new TreeBuilder(siz + 1, siz);
        for (int i = 0; i < siz; i++) {
            tb.addEdge(i, next[i]);
        }
        EulerTour et = new EulerTour(tb.build());
        int[] beg = et.tourBeg;
        int[] end = et.tourEnd;
        int[] tour = et.tour;
        int[] w = new int[2 * siz + 2];
        for (int i = 0; i < 2 * siz + 2; i++) {
            if (tour[i] < 0) {
                if (~tour[i] == siz) {
                    w[i] = 0;
                } else {
                    w[i] = -p[~tour[i]].trd;
                }
            } else {
                if (tour[i] == siz) {
                    w[i] = 0;
                } else {
                    w[i] = p[tour[i]].trd;
                }
            }
            if (i > 0) {
                w[i] += w[i - 1];
            }
        }
        for (int i = 0; i < siz; i++) {
            if (p[i].fst > a) break;
            int dst = d.stepUntil(i, j -> j == siz || p[j].snd >= b);
            if (dst == siz) continue;
            int fr, to;
            if (beg[i] >= dst) {
                fr = beg[dst];
                to = beg[i];
            } else {
                fr = beg[i];
                to = beg[dst];
            }
            min = Math.min(min, fr > 0 ? w[to] - w[fr - 1] : w[to]);
        }
        if (min == Const.IINF) {
            pw.println(-1);
        } else {
            pw.println(min);
        }
    }
}
/**
 * @verified
 * - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D
 */
class EulerTour {
    private final int n;
    public final int[] tour;
    public final int[] tourBeg;
    public final int[] tourEnd;
    public final int[] subtBeg;
    public final int[] subtEnd;

    public EulerTour(Tree t) {
        this.n = t.getV();
        this.tour = new int[n << 1];
        this.tourBeg = new int[n];
        this.tourEnd = new int[n];
        this.subtBeg = new int[n];
        this.subtEnd = new int[n];
        build(t);
    }

    private void build(Tree t) {
        java.util.Arrays.fill(tourBeg, -1);
        int[] pre = t.preOrder();
        int[] pst = t.postOrder();
        for (int i = 0, j = 0; j != n;) {
            int u = pst[j], v;
            do {
                v = pre[i];
                tour[i + j] = v;
                tourBeg[v] = i + j;
                subtBeg[v] = i;
                i++;
            } while (v != u);
            do {
                tour[i + j] = ~u;
                tourEnd[u] = i + j;
                subtEnd[u] = i;
                j++;
            } while (j < n && tourBeg[u = pst[j]] >= 0);
        }
    }
}

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

class TreeBuilder {
    private static final class TreeEdge {
        final int from, to;
        final long cost;
        TreeEdge(int from, int to, long cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }
    private final int n;
    private int ptr = 0;
    private final int root;
    private final TreeEdge[] edges;
    private final int[] count;
    private final int[][] adj;
    public TreeBuilder(int n, int root) {
        this.n = n;
        this.root = root;
        this.edges = new TreeEdge[n - 1];
        this.count = new int[n];
        this.adj = new int[n][];
    }
    public TreeBuilder(int n) {
        this(n, 0);
    }
    public void addEdge(int u, int v, long cost) {
        edges[ptr++] = new TreeEdge(u, v, cost);
        count[u]++;
        count[v]++;
    }
    public void addEdge(int u, int v) {
        addEdge(u, v, 1);
    }
    public Tree build() {
        for (int i = 0; i < n; i++) {
            adj[i] = new int[count[i]];
        }
        for (TreeEdge 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() {
        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 (TreeEdge 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
 */
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
 */
@FunctionalInterface
interface IntBiPredicate {
    static final int INT_BIT = 32;
    static final long MASK = 0xffff_ffffl;
    public boolean test(int x, int y);
    default public IntPredicate curry(final int x) {return y -> test(x, y);}
    default public LongPredicate toLongPredicate() {return l -> test((int) (l >>> INT_BIT), (int) (l & MASK));}
    default public IntBiPredicate negate() {return (x, y) -> !test(x, y);}
    default public IntBiPredicate and(final IntBiPredicate other) {return (x, y) -> test(x, y) && other.test(x, y);}
    default public IntBiPredicate or(final IntBiPredicate other) {return (x, y) -> test(x, y) || other.test(x, y);}
    default public IntBiPredicate xor(final IntBiPredicate other) {return (x, y) -> test(x, y) ^ other.test(x, y);}
}

class Const {
    public static final long   LINF   = 1l << 59;
    public static final int    IINF   = (1  << 30) - 1;
    public static final double DINF   = 1e150;
    
    public static final double SMALL  = 1e-12;
    public static final double MEDIUM = 1e-9;
    public static final double LARGE  = 1e-6;

    public static final long MOD1000000007 = 1000000007;
    public static final long MOD998244353  = 998244353 ;
    public static final long MOD754974721  = 754974721 ;
    public static final long MOD167772161  = 167772161 ;
    public static final long MOD469762049  = 469762049 ;

    public static final int[] dx8 = {1, 0, -1, 0, 1, -1, -1, 1};
    public static final int[] dy8 = {0, 1, 0, -1, 1, 1, -1, -1};
    public static final int[] dx4 = {1, 0, -1, 0};
    public static final int[] dy4 = {0, 1, 0, -1};
}
/**
 * @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
 */
final class IntPair3 {
    public int fst, snd, trd;
    public IntPair3(final int fst, final int snd, final int trd) {this.fst = fst; this.snd = snd; this.trd = trd;}
    @Override @SuppressWarnings("all")
    public boolean equals(final Object o) {
        if (this == o) return true;
        if (!(o instanceof IntPair3)) return false;
        final IntPair3 p = (IntPair3) o;
        return this.fst == p.fst && this.snd == p.snd && this.trd == p.trd;
    }
    @Override
    public int hashCode() {return Objects.hash(this.fst, this.snd, this.trd);}
    @Override
    public String toString() {return "(" + this.fst + ", " + this.snd + ", " + this.trd + ")";}
}


/**
 * @author https://atcoder.jp/users/suisen
 */
final class Longs {
    private Longs(){}
    public static long max(long a, long b) {
        return Math.max(a, b);
    }
    public static long max(long a, long b, long c) {
        return Math.max(Math.max(a, b), c);
    }
    public static long max(long a, long b, long c, long d) {
        return Math.max(Math.max(Math.max(a, b), c), d);
    }
    public static long max(long a, long b, long c, long d, long e) {
        return Math.max(Math.max(Math.max(Math.max(a, b), c), d), e);
    }
    public static long max(long a, long b, long c, long d, long e, long f) {
        return Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f);
    }
    public static long max(long a, long b, long c, long d, long e, long f, long g) {
        return Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f), g);
    }
    public static long max(long a, long b, long c, long d, long e, long f, long g, long h) {
        return Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f), g), h);
    }
    public static long max(long a, long... vals) {
        long ret = a; for (long e : vals) ret = Math.max(ret, e);
        return ret;
    }
    public static long min(long a, long b) {
        return Math.min(a, b);
    }
    public static long min(long a, long b, long c) {
        return Math.min(Math.min(a, b), c);
    }
    public static long min(long a, long b, long c, long d) {
        return Math.min(Math.min(Math.min(a, b), c), d);
    }
    public static long min(long a, long b, long c, long d, long e) {
        return Math.min(Math.min(Math.min(Math.min(a, b), c), d), e);
    }
    public static long min(long a, long b, long c, long d, long e, long f) {
        return Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f);
    }
    public static long min(long a, long b, long c, long d, long e, long f, long g) {
        return Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f), g);
    }
    public static long min(long a, long b, long c, long d, long e, long f, long g, long h) {
        return Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f), g), h);
    }
    public static long min(long a, long... vals) {
        long ret = a; for (long e : vals) ret = Math.min(ret, e);
        return ret;
    }
    public static long fold(final LongBinaryOperator func, final long... a) {
        long ret = a[0]; for (int i = 1; i < a.length; i++) ret = func.applyAsLong(ret, a[i]);
        return ret;
    }
    public static boolean isPowerOfTwo(final long n) {return n != 0 && (-n & n) == n;}
    public static int ceilExponent(final long n) {return 63 - Long.numberOfLeadingZeros(n) + (isPowerOfTwo(n) ? 0 : 1);}
    public static int floorExponent(final long n) {return 63 - Long.numberOfLeadingZeros(n) + (n == 0 ? 1 : 0);}
    public static int ceilExponent(final long n, final int base) {
        if (base == 2) return ceilExponent(n);
        int i = 0;
        long m = 1;
        while (m < n) {
            i++;
            final long r = m * base;
            if ((m | base) >> 31 != 0 && r / base != m) break;
            m = r;
        }
        return i;
    }
    /**
     * Caluculate the ceil of a/b. Returns the smallest integer greater than or
     * equal to a/b while 'a/b' rounds fractional parts to ZERO.
     * @param a
     * @param b
     * @return the smallest integer greater than or equal to a/b
     */
    public static long cld(final long a, final long b) {
        if (a > 0 && b > 0) return (a + b - 1) / b;
        if (a < 0 && b < 0) return (a + b + 1) / b;
        return a / b;
    }

    /**
     * Caluculate the floor of a/b. Returns the largest integer less than or equal
     * to a/b while 'a/b' rounds fractional parts to ZERO.
     * @param a
     * @param b
     * @return the largest integer less than or equal to a/b
     */
    public static long fld(final long a, final long b) {
        if (a <= 0 && b > 0) return (a - b + 1) / b;
        if (a > 0 && b <= 0) return (a - b - 1) / b;
        return a / b;
    }
    public static String join(final String sep, final long... a) {
        final StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            sb.append(a[i]);
            if (i < a.length - 1) sb.append(sep);
        }
        return sb.toString();
    }
}



/**
 * @author https://atcoder.jp/users/suisen
 */
final class Doubling {
    public final int[][] doubling;
    private final int height;
    private final int n;
    public Doubling(final int[] a, final long maxStep) {
        this.n = a.length;
        this.height = Longs.ceilExponent(maxStep) + 2;
        this.doubling = new int[height][n];
        build(a);
    }
    public int getHeight() {return height;}
    public int query(int i, long step) {
        int h = height - 1;
        while (step > 0) {
            if ((step & (1l << h)) != 0) {
                i = doubling[h][i];
                step ^= 1l << h;
            }
            h--;
        }
        return i;
    }
    public int stepWhile(int i, final IntPredicate p) {
        int h = height - 1;
        while (h >= 0) {
            if (p.test(doubling[h][i])) i = doubling[h][i];
            h--;
        }
        return i;
    }
    public int stepUntil(final int i, final IntPredicate p) {return p.test(i) ? i : doubling[0][stepWhile(i, p.negate())];}
    public int[] biStep(final int u, final int v, final int exponent) {
        final int us = doubling[exponent][u];
        final int vs = doubling[exponent][v];
        return new int[]{us, vs};
    }
    private long biStep(final long uv, final int exponent) {
        final int u = (int) (uv >>> 32);
        final int v = (int) (uv & 0xffff_ffffl);
        return (long) doubling[exponent][u] << 32 | doubling[exponent][v];
    }
    public int[] biStepWhile(final int u, final int v, final IntBiPredicate p) {
        final long ret = biStepWhile((long) u << 32 | v, p.toLongPredicate());
        return new int[]{(int) (ret >> 32), (int) (ret & 0xffff_ffffl)};
    }
    private long biStepWhile(long uv, final LongPredicate p) {
        int h = height - 1;
        while (h >= 0) {
            final long step = biStep(uv, h);
            if (p.test(step)) {
                uv = step;
            }
            h--;
        }
        return uv;
    }
    public int[] biStepUntil(final int u, final int v, final IntBiPredicate p) {
        final long ret = biStepUntil((long) u << 32 | v, p.toLongPredicate());
        return new int[]{(int) (ret >> 32), (int) (ret & 0xffff_ffffl)};
    }
    private long biStepUntil(final long uv, final LongPredicate p) {return p.test(uv) ? uv : biStep(biStepWhile(uv, p.negate()), 0);}
    public int[] parallelStep(final int[] a, final int exponent) {
        final int[] ret = a.clone();
        for (int i = 0; i < a.length; i++) ret[i] = doubling[exponent][a[i]];
        return ret;
    }
    private void build(final int[] a) {
        doubling[0] = a;
        for (int h = 1; h < height; h++) for (int i = 0; i < n; i++) doubling[h][i] = doubling[h - 1][doubling[h - 1][i]];
    }
}
/**
 * @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];
    }
}