Problem: Barney is searching for his dream girl. He lives in NYC. NYC has n junctions numbered from 1 to n and n - 1 roads connecting them. We will consider the NYC as a rooted tree with root being junction 1. m girls live in NYC, i-th of them lives along junction ci and her weight initially equals i pounds.

<image>

Barney consider a girl x to be better than a girl y if and only if: girl x has weight strictly less than girl y or girl x and girl y have equal weights and index of girl x living junction index is strictly less than girl y living junction index, i.e. cx < cy. Thus for any two girls one of them is always better than another one.

For the next q days, one event happens each day. There are two types of events:

  1. Barney goes from junction v to junction u. As a result he picks at most k best girls he still have not invited from junctions on his way and invites them to his house to test if one of them is his dream girl. If there are less than k not invited girls on his path, he invites all of them.
  2. Girls living along junctions in subtree of junction v (including v itself) put on some weight. As result, their weights increase by k pounds. 



Your task is for each event of first type tell Barney the indices of girls he will invite to his home in this event.

Input

The first line of input contains three integers n, m and q (1 ≤ n, m, q ≤ 105) — the number of junctions in NYC, the number of girls living in NYC and the number of events respectively.

The next n - 1 lines describes the roads. Each line contains two integers v and u (1 ≤ v, u ≤ n, v ≠ u) meaning that there is a road connecting junctions v and u .

The next line contains m integers c1, c2, ..., cm (1 ≤ ci ≤ n) — the girl's living junctions.

The next q lines describe the events in chronological order. Each line starts with an integer t (1 ≤ t ≤ 2) — type of the event .

If t = 1 then the line describes event of first type three integers v, u and k (1 ≤ v, u, k ≤ n) follow — the endpoints of Barney's path and the number of girls that he will invite at most.

Otherwise the line describes event of second type and two integers v and k (1 ≤ v ≤ n, 1 ≤ k ≤ 109) follow — the root of the subtree and value by which all the girls' weights in the subtree should increase.

Output

For each event of the first type, print number t and then t integers g1, g2, ..., gt in one line, meaning that in this event Barney will invite t girls whose indices are g1, ..., gt in the order from the best to the worst according to Barney's considerations.

Example

Input

5 7 11
3 5
2 3
4 3
1 4
4 1 4 5 4 1 4
2 4 3
1 2 1 2
1 4 2 1
2 2 10
2 1 10
1 2 4 1
1 2 3 4
2 5 2
2 4 9
1 3 5 2
1 1 2 3


Output

2 2 1 
1 3 
1 5 
0 
1 4 
2 6 7 

Note

For the first sample case:

<image>

Description of events:

  1. Weights of girls in subtree of junction 4 increase by 3. These girls have IDs: 1, 3, 5, 4, 7. 
  2. Barney goes from junction 2 to 1. Girls on his way have IDs 1, 2, 3, 5, 6, 7 with weights 4, 2, 6, 8, 6, 10 respectively. So, he invites girls 2 and 1. 
  3. Barney goes from junction 4 to junction 2. Girls on his way has IDs 3, 5, 7 with weights 6, 8, 10 respectively. So he invites girl 3. 
  4. Weight of girls in subtree of junction 2 increase by 10. There are no not invited girls, so nothing happens. 
  5. Weight of girls in subtree of junction 1 increase by 10. These girls (all girls left) have IDs: 4, 5, 6, 7. 
  6. Barney goes from junction 2 to junction 4. Girls on his way has IDs 5, 7 with weights 18, 20 respectively. So he invites girl 5. 
  7. Barney goes from junction 2 to junction 3. There is no girl on his way. 
  8. Weight of girls in subtree of junction 5 increase by 2. The only girl there is girl with ID 4. 
  9. Weight of girls in subtree of junction 4 increase by 9. These girls have IDs: 4, 6, 7. 
  10. Barney goes from junction 3 to junction 5. Only girl on his way is girl with ID 4. 
  11. Barney goes from junction 1 to junction 2. Girls on his way has IDs 6, 7 with weights 16, 29 respectively. 

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        final static long inf = (long) 1e16;
        int n;
        int cntG;
        int q;
        Graph gr;
        IntArrayList[] idsGirls;
        int[] vertexCount;
        int[] parent;
        int[] depth;
        int[] leader;
        int[] posLSub;
        int[] posRSub;
        int[] posRVertex;
        int[] posGirl;
        int szOrder;
        long[] orderWeight;
        int[] orderIdGirl;
        long[] treeDelta;
        long[] treeWeight;
        int[] treeIdGirl;
        long[] ansWeight;
        int[] ansIdGirl;
        OutputWriter out;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            this.out = out;
            n = in.readInt();
            cntG = in.readInt();
            q = in.readInt();

            gr = new BidirectionalGraph(n, n - 1);
            for (int iter = 0; iter < n - 1; iter++) {
                gr.addSimpleEdge(in.readInt() - 1, in.readInt() - 1);
            }

            idsGirls = new IntArrayList[n];
            for (int i = 0; i < n; i++) {
                idsGirls[i] = new IntArrayList();
            }
            for (int i = 0; i < cntG; i++) {
                idsGirls[in.readInt() - 1].add(i);
            }


            vertexCount = new int[n];
            parent = new int[n];
            depth = new int[n];
            initSzAndParentAndDepth(0, -1);

            leader = new int[n];
            posLSub = new int[n];
            posRSub = new int[n];
            posRVertex = new int[n];
            posGirl = new int[cntG];
            orderIdGirl = new int[n + cntG];
            orderWeight = new long[n + cntG];

            heavyLightDecomp(0, -1, 0);
            {
                int sz = Integer.highestOneBit(szOrder) << 2;
                treeDelta = new long[sz];
                treeIdGirl = new int[sz];
                treeWeight = new long[sz];
                ansIdGirl = new int[sz];
                ansWeight = new long[sz];
            }
            build(0, 0, szOrder - 1);

        /*/
        //for (int v = 0; v < n; v++) {
        IntArrayList answer = new IntArrayList();
        for (; ; ) {
            int girl = getGirl(1, 1);
            if (girl == -1) {
                break;
            }
            answer.add(girl);
        }
        out.print(answer.size());
        for (int idG : answer) {
            out.print(" ");
            out.print(idG + 1);
        }
        out.printLine();
        //}
        /**/


            //
            for (int iter = 0; iter < q; iter++) {
                int op = in.readInt();
                if (op == 1) {
                    int a = in.readInt() - 1;
                    int b = in.readInt() - 1;
                    int k = in.readInt();

                    IntArrayList answer = new IntArrayList();
                    for (int iteration = 0; iteration < k; iteration++) {
                        int girl = getGirl(a, b);
                        if (girl == -1) {
                            break;
                        }
                        answer.add(girl);
                    }

                    out.print(answer.size());
                    for (int idG : answer) {
                        out.print(" ");
                        out.print(idG + 1);
                    }
                    out.printLine();
                } else if (op == 2) {
                    int v = in.readInt() - 1;
                    int delta = in.readInt();
                    addDelta(0, 0, szOrder - 1, posLSub[v], posRSub[v], delta);
                }
            }
        /**/
        }

        private int getGirl(int d, int u) {
            long w = inf;
            int id = -1;
            for (; ; ) {
                if (leader[d] == leader[u]) {
                    if (depth[d] < depth[u]) {
                        int t = d;
                        d = u;
                        u = t;
                    }
                    query(0, 0, szOrder - 1, posLSub[u], posRVertex[d]);
                    if (w > ansWeight[0] || w == ansWeight[0] && id > ansIdGirl[0]) {
                        w = ansWeight[0];
                        id = ansIdGirl[0];
                    }
                    break;
                } else {
                    if (depth[leader[d]] < depth[leader[u]]) {
                        int t = d;
                        d = u;
                        u = t;
                    }
                    query(0, 0, szOrder - 1, posLSub[leader[d]], posRVertex[d]);
                    d = parent[leader[d]];

                    if (w > ansWeight[0] || w == ansWeight[0] && id > ansIdGirl[0]) {
                        w = ansWeight[0];
                        id = ansIdGirl[0];
                    }
                }
            }
            if (id != -1) {
                addDelta(0, 0, szOrder - 1, posGirl[id], posGirl[id], inf - w);
            }
            return id;
        }

        private void query(int v, int tl, int tr, int l, int r) {
            if (l > r) {
                ansWeight[v] = inf;
                ansIdGirl[v] = -1;
                return;
            }

            if (tl == l && tr == r) {
                ansWeight[v] = treeWeight[v];
                ansIdGirl[v] = treeIdGirl[v];
            } else {
                push(v);
                int tm = (tl + tr) >> 1;
                query(v + v + 1, tl, tm, l, Math.min(r, tm));
                query(v + v + 2, tm + 1, tr, Math.max(l, tm + 1), r);
                upd(v, ansWeight, ansIdGirl);
            }
        }

        private void addDelta(int v, int tl, int tr, int l, int r, long delta) {
            if (l > r) {
                return;
            }

            if (tl == l && tr == r) {
                treeWeight[v] += delta;
                treeDelta[v] += delta;
            } else {
                push(v);
                int tm = (tl + tr) >> 1;
                addDelta(v + v + 1, tl, tm, l, Math.min(r, tm), delta);
                addDelta(v + v + 2, tm + 1, tr, Math.max(l, tm + 1), r, delta);
                upd(v, treeWeight, treeIdGirl);
            }
        }

        private void build(int v, int tl, int tr) {
            if (tl == tr) {
                treeWeight[v] = orderWeight[tl];
                treeIdGirl[v] = orderIdGirl[tl];
            } else {
                push(v);
                int tm = (tl + tr) >> 1;
                build(v + v + 1, tl, tm);
                build(v + v + 2, tm + 1, tr);
                upd(v, treeWeight, treeIdGirl);
            }
        }

        private void upd(int v, long[] weight, int[] idGirl) {
            int vl = v + v + 1;
            int vr = v + v + 2;
            if (weight[vl] < weight[vr] || weight[vl] == weight[vr] && idGirl[vl] < idGirl[vr]) {
                weight[v] = weight[vl];
                idGirl[v] = idGirl[vl];
            } else {
                weight[v] = weight[vr];
                idGirl[v] = idGirl[vr];
            }
        }

        private void push(int v) {
            add(v + v + 1, treeDelta[v]);
            add(v + v + 2, treeDelta[v]);
            treeDelta[v] = 0;
        }

        private void add(int v, long delta) {
            treeDelta[v] += delta;
            treeWeight[v] += delta;
        }

        private void initSzAndParentAndDepth(int v, int p) {
            vertexCount[v] = 1;
            parent[v] = p;
            if (p != -1) {
                depth[v] = depth[p] + 1;
            }
            for (Edge edge : gr.outbound(v)) {
                int to = edge.getDestination();
                if (to == p) {
                    continue;
                }
                initSzAndParentAndDepth(to, v);
                vertexCount[v] += vertexCount[to];
            }
        }

        void heavyLightDecomp(int v, int parent, int leader) {
            this.leader[v] = leader;

            posLSub[v] = szOrder;

            orderIdGirl[szOrder] = -1;
            orderWeight[szOrder] = inf;
            ++szOrder;

            for (int idG : idsGirls[v]) {
                orderIdGirl[szOrder] = idG;
                orderWeight[szOrder] = idG + 1;
                posGirl[idG] = szOrder;
                ++szOrder;
            }

            posRVertex[v] = szOrder - 1;

            int bestTo = -1;
            for (Edge edge : gr.outbound(v)) {
                int to = edge.getDestination();
                if (to == parent) {
                    continue;
                }
                if (bestTo == -1 || vertexCount[bestTo] < vertexCount[to]) {
                    bestTo = to;
                }
            }

            if (bestTo != -1) {
                heavyLightDecomp(bestTo, v, leader);
                for (Edge edge : gr.outbound(v)) {
                    int to = edge.getDestination();
                    if (to == parent) {
                        continue;

                    }
                    if (bestTo != to) {
                        heavyLightDecomp(to, v, to);
                    }
                }
            }

            posRSub[v] = szOrder - 1;
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine() {
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void print(int i) {
            writer.print(i);
        }

    }

    static class IntArrayList extends IntAbstractStream implements IntList {
        private int size;
        private int[] data;

        public IntArrayList() {
            this(3);
        }

        public IntArrayList(int capacity) {
            data = new int[capacity];
        }

        public IntArrayList(IntCollection c) {
            this(c.size());
            addAll(c);
        }

        public IntArrayList(IntStream c) {
            this();
            if (c instanceof IntCollection) {
                ensureCapacity(((IntCollection) c).size());
            }
            addAll(c);
        }

        public IntArrayList(IntArrayList c) {
            size = c.size();
            data = c.data.clone();
        }

        public IntArrayList(int[] arr) {
            size = arr.length;
            data = arr.clone();
        }

        public int size() {
            return size;
        }

        public int get(int at) {
            if (at >= size) {
                throw new IndexOutOfBoundsException("at = " + at + ", size = " + size);
            }
            return data[at];
        }

        private void ensureCapacity(int capacity) {
            if (data.length >= capacity) {
                return;
            }
            capacity = Math.max(2 * data.length, capacity);
            data = Arrays.copyOf(data, capacity);
        }

        public void addAt(int index, int value) {
            ensureCapacity(size + 1);
            if (index > size || index < 0) {
                throw new IndexOutOfBoundsException("at = " + index + ", size = " + size);
            }
            if (index != size) {
                System.arraycopy(data, index, data, index + 1, size - index);
            }
            data[index] = value;
            size++;
        }

        public void removeAt(int index) {
            if (index >= size || index < 0) {
                throw new IndexOutOfBoundsException("at = " + index + ", size = " + size);
            }
            if (index != size - 1) {
                System.arraycopy(data, index + 1, data, index, size - index - 1);
            }
            size--;
        }

    }

    static interface Edge {
        public int getDestination();

    }

    static interface IntList extends IntReversableCollection {
        public abstract int get(int index);

        public abstract void addAt(int index, int value);

        public abstract void removeAt(int index);

        default public IntIterator intIterator() {
            return new IntIterator() {
                private int at;
                private boolean removed;

                public int value() {
                    if (removed) {
                        throw new IllegalStateException();
                    }
                    return get(at);
                }

                public boolean advance() {
                    at++;
                    removed = false;
                    return isValid();
                }

                public boolean isValid() {
                    return !removed && at < size();
                }

                public void remove() {
                    removeAt(at);
                    at--;
                    removed = true;
                }
            };
        }


        default public void add(int value) {
            addAt(size(), value);
        }

    }

    static abstract class IntAbstractStream implements IntStream {

        public String toString() {
            StringBuilder builder = new StringBuilder();
            boolean first = true;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                if (first) {
                    first = false;
                } else {
                    builder.append(' ');
                }
                builder.append(it.value());
            }
            return builder.toString();
        }


        public boolean equals(Object o) {
            if (!(o instanceof IntStream)) {
                return false;
            }
            IntStream c = (IntStream) o;
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                if (it.value() != jt.value()) {
                    return false;
                }
                it.advance();
                jt.advance();
            }
            return !it.isValid() && !jt.isValid();
        }


        public int hashCode() {
            int result = 0;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                result *= 31;
                result += it.value();
            }
            return result;
        }

    }

    static class Graph {
        public static final int REMOVED_BIT = 0;
        protected int vertexCount;
        protected int edgeCount;
        private int[] firstOutbound;
        private int[] firstInbound;
        private Edge[] edges;
        private int[] nextInbound;
        private int[] nextOutbound;
        private int[] from;
        private int[] to;
        private long[] weight;
        public long[] capacity;
        private int[] reverseEdge;
        private int[] flags;

        public Graph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public Graph(int vertexCount, int edgeCapacity) {
            this.vertexCount = vertexCount;
            firstOutbound = new int[vertexCount];
            Arrays.fill(firstOutbound, -1);

            from = new int[edgeCapacity];
            to = new int[edgeCapacity];
            nextOutbound = new int[edgeCapacity];
            flags = new int[edgeCapacity];
        }

        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            ensureEdgeCapacity(edgeCount + 1);
            if (firstOutbound[fromID] != -1) {
                nextOutbound[edgeCount] = firstOutbound[fromID];
            } else {
                nextOutbound[edgeCount] = -1;
            }
            firstOutbound[fromID] = edgeCount;
            if (firstInbound != null) {
                if (firstInbound[toID] != -1) {
                    nextInbound[edgeCount] = firstInbound[toID];
                } else {
                    nextInbound[edgeCount] = -1;
                }
                firstInbound[toID] = edgeCount;
            }
            this.from[edgeCount] = fromID;
            this.to[edgeCount] = toID;
            if (capacity != 0) {
                if (this.capacity == null) {
                    this.capacity = new long[from.length];
                }
                this.capacity[edgeCount] = capacity;
            }
            if (weight != 0) {
                if (this.weight == null) {
                    this.weight = new long[from.length];
                }
                this.weight[edgeCount] = weight;
            }
            if (reverseEdge != -1) {
                if (this.reverseEdge == null) {
                    this.reverseEdge = new int[from.length];
                    Arrays.fill(this.reverseEdge, 0, edgeCount, -1);
                }
                this.reverseEdge[edgeCount] = reverseEdge;
            }
            if (edges != null) {
                edges[edgeCount] = createEdge(edgeCount);
            }
            return edgeCount++;
        }

        protected final GraphEdge createEdge(int id) {
            return new GraphEdge(id);
        }

        public final int addFlowWeightedEdge(int from, int to, long weight, long capacity) {
            if (capacity == 0) {
                return addEdge(from, to, weight, 0, -1);
            } else {
                int lastEdgeCount = edgeCount;
                addEdge(to, from, -weight, 0, lastEdgeCount + entriesPerEdge());
                return addEdge(from, to, weight, capacity, lastEdgeCount);
            }
        }

        protected int entriesPerEdge() {
            return 1;
        }

        public final int addWeightedEdge(int from, int to, long weight) {
            return addFlowWeightedEdge(from, to, weight, 0);
        }

        public final int addSimpleEdge(int from, int to) {
            return addWeightedEdge(from, to, 0);
        }

        protected final int edgeCapacity() {
            return from.length;
        }

        public final int destination(int id) {
            return to[id];
        }

        protected final void initEdges() {
            if (edges == null) {
                edges = new Edge[from.length];
                for (int i = 0; i < edgeCount; i++) {
                    edges[i] = createEdge(i);
                }
            }
        }

        public final boolean flag(int id, int bit) {
            return (flags[id] >> bit & 1) != 0;
        }

        public final void setFlag(int id, int bit) {
            flags[id] |= 1 << bit;
        }

        public final void removeEdge(int id) {
            setFlag(id, REMOVED_BIT);
        }

        public final boolean isRemoved(int id) {
            return flag(id, REMOVED_BIT);
        }

        public final Iterable<Edge> outbound(final int id) {
            initEdges();
            return new Iterable<Edge>() {
                public Iterator<Edge> iterator() {
                    return new EdgeIterator(id, firstOutbound, nextOutbound);
                }
            };
        }

        protected void ensureEdgeCapacity(int size) {
            if (from.length < size) {
                int newSize = Math.max(size, 2 * from.length);
                if (edges != null) {
                    edges = resize(edges, newSize);
                }
                from = resize(from, newSize);
                to = resize(to, newSize);
                nextOutbound = resize(nextOutbound, newSize);
                if (nextInbound != null) {
                    nextInbound = resize(nextInbound, newSize);
                }
                if (weight != null) {
                    weight = resize(weight, newSize);
                }
                if (capacity != null) {
                    capacity = resize(capacity, newSize);
                }
                if (reverseEdge != null) {
                    reverseEdge = resize(reverseEdge, newSize);
                }
                flags = resize(flags, newSize);
            }
        }

        protected final int[] resize(int[] array, int size) {
            int[] newArray = new int[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private long[] resize(long[] array, int size) {
            long[] newArray = new long[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private Edge[] resize(Edge[] array, int size) {
            Edge[] newArray = new Edge[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        protected class GraphEdge implements Edge {
            protected int id;

            protected GraphEdge(int id) {
                this.id = id;
            }

            public int getDestination() {
                return destination(id);
            }

        }

        public class EdgeIterator implements Iterator<Edge> {
            private int edgeID;
            private final int[] next;
            private int lastID = -1;

            public EdgeIterator(int id, int[] first, int[] next) {
                this.next = next;
                edgeID = nextEdge(first[id]);
            }

            private int nextEdge(int id) {
                while (id != -1 && isRemoved(id)) {
                    id = next[id];
                }
                return id;
            }

            public boolean hasNext() {
                return edgeID != -1;
            }

            public Edge next() {
                if (edgeID == -1) {
                    throw new NoSuchElementException();
                }
                lastID = edgeID;
                edgeID = nextEdge(next[lastID]);
                return edges[lastID];
            }

            public void remove() {
                if (lastID == -1) {
                    throw new IllegalStateException();
                }
                removeEdge(lastID);
                lastID = -1;
            }

        }

    }

    static interface IntCollection extends IntStream {
        public int size();

        default public void add(int value) {
            throw new UnsupportedOperationException();
        }

        default public IntCollection addAll(IntStream values) {
            for (IntIterator it = values.intIterator(); it.isValid(); it.advance()) {
                add(it.value());
            }
            return this;
        }

    }

    static class BidirectionalGraph extends Graph {
        public int[] transposedEdge;

        public BidirectionalGraph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public BidirectionalGraph(int vertexCount, int edgeCapacity) {
            super(vertexCount, 2 * edgeCapacity);
            transposedEdge = new int[2 * edgeCapacity];
        }


        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            int lastEdgeCount = edgeCount;
            super.addEdge(fromID, toID, weight, capacity, reverseEdge);
            super.addEdge(toID, fromID, weight, capacity, reverseEdge == -1 ? -1 : reverseEdge + 1);
            this.transposedEdge[lastEdgeCount] = lastEdgeCount + 1;
            this.transposedEdge[lastEdgeCount + 1] = lastEdgeCount;
            return lastEdgeCount;
        }


        protected int entriesPerEdge() {
            return 2;
        }


        protected void ensureEdgeCapacity(int size) {
            if (size > edgeCapacity()) {
                super.ensureEdgeCapacity(size);
                transposedEdge = resize(transposedEdge, edgeCapacity());
            }
        }

    }

    static interface IntReversableCollection extends IntCollection {
    }

    static interface IntIterator {
        public int value() throws NoSuchElementException;

        public boolean advance();

        public boolean isValid();

    }

    static interface IntStream extends Iterable<Integer>, Comparable<IntStream> {
        public IntIterator intIterator();

        default public Iterator<Integer> iterator() {
            return new Iterator<Integer>() {
                private IntIterator it = intIterator();

                public boolean hasNext() {
                    return it.isValid();
                }

                public Integer next() {
                    int result = it.value();
                    it.advance();
                    return result;
                }
            };
        }

        default public int compareTo(IntStream c) {
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                int i = it.value();
                int j = jt.value();
                if (i < j) {
                    return -1;
                } else if (i > j) {
                    return 1;
                }
                it.advance();
                jt.advance();
            }
            if (it.isValid()) {
                return 1;
            }
            if (jt.isValid()) {
                return -1;
            }
            return 0;
        }

    }
}