gt:                 id = next[id];
context: package template.egork.graph;
  
  import java.util.Arrays;
  import java.util.Iterator;
  import java.util.NoSuchElementException;
  
  /**
   * @author Egor Kulikov (egorku@yandex-team.ru)
   */
  public 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 static Graph createGraph(int vertexCount, int[] from, int[] to) {
          Graph graph = new Graph(vertexCount, from.length);
          for (int i = 0; i < from.length; i++) {
              graph.addSimpleEdge(from[i], to[i]);
          }
          return graph;
      }
  
      public static Graph createWeightedGraph(int vertexCount, int[] from, int[] to, long[] weight) {
          Graph graph = new Graph(vertexCount, from.length);
          for (int i = 0; i < from.length; i++) {
              graph.addWeightedEdge(from[i], to[i], weight[i]);
          }
          return graph;
      }
  
      public static Graph createFlowGraph(int vertexCount, int[] from, int[] to, long[] capacity) {
          Graph graph = new Graph(vertexCount, from.length * 2);
          for (int i = 0; i < from.length; i++) {
              graph.addFlowEdge(from[i], to[i], capacity[i]);
          }
          return graph;
      }
  
      public static Graph createFlowWeightedGraph(int vertexCount, int[] from, int[] to, long[] weight, long[] capacity) {
          Graph graph = new Graph(vertexCount, from.length * 2);
          for (int i = 0; i < from.length; i++) {
              graph.addFlowWeightedEdge(from[i], to[i], weight[i], capacity[i]);
          }
          return graph;
      }
  
      public static Graph createTree(int[] parent) {
          Graph graph = new Graph(parent.length + 1, parent.length);
          for (int i = 0; i < parent.length; i++) {
              graph.addSimpleEdge(parent[i], i + 1);
          }
          return graph;
      }
  
      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 addFlowEdge(int from, int to, long capacity) {
          return addFlowWeightedEdge(from, to, 0, capacity);
      }
  
      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);
      }
  
      public final int vertexCount() {
          return vertexCount;
      }
  
      public final int edgeCount() {
          return edgeCount;
      }
  
      protected final int edgeCapacity() {
          return from.length;
      }
  
      public final Edge edge(int id) {
          initEdges();
          return edges[id];
      }
  
      public final int firstOutbound(int vertex) {
          int id = firstOutbound[vertex];
          while (id != -1 && isRemoved(id)) {
              id = nextOutbound[id];
          }
          return id;
      }
  
      public final int nextOutbound(int id) {
          id = nextOutbound[id];
          while (id != -1 && isRemoved(id)) {
              id = nextOutbound[id];
          }
          return id;
      }
  
      public final int firstInbound(int vertex) {
          initInbound();
          int id = firstInbound[vertex];
          while (id != -1 && isRemoved(id)) {
              id = nextInbound[id];
          }
          return id;
      }
  
      public final int nextInbound(int id) {
          initInbound();
          id = nextInbound[id];
          while (id != -1 && isRemoved(id)) {
              id = nextInbound[id];
          }
          return id;
      }
  
      public final int source(int id) {
          return from[id];
      }
  
      public final int destination(int id) {
          return to[id];
      }
  
      public final long weight(int id) {
          if (weight == null) {
              return 0;
          }
          return weight[id];
      }
  
      public final long capacity(int id) {
          if (capacity == null) {
              return 0;
          }
          return capacity[id];
      }
  
      public final long flow(int id) {
          if (reverseEdge == null) {
              return 0;
          }
          return capacity[reverseEdge[id]];
      }
  
      public final void pushFlow(int id, long flow) {
          if (flow == 0) {
              return;
          }
          if (flow > 0) {
              if (capacity(id) < flow) {
                  throw new IllegalArgumentException("Not enough capacity");
              }
          } else {
              if (flow(id) < -flow) {
                  throw new IllegalArgumentException("Not enough capacity");
              }
          }
          capacity[id] -= flow;
          capacity[reverseEdge[id]] += flow;
      }
  
      public int transposed(int id) {
          return -1;
      }
  
      public final int reverse(int id) {
          if (reverseEdge == null) {
              return -1;
          }
          return reverseEdge[id];
      }
  
      public final void addVertices(int count) {
          ensureVertexCapacity(vertexCount + count);
          Arrays.fill(firstOutbound, vertexCount, vertexCount + count, -1);
          if (firstInbound != null) {
              Arrays.fill(firstInbound, vertexCount, vertexCount + count, -1);
          }
          vertexCount += count;
      }
  
      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 void removeVertex(int vertex) {
          int id = firstOutbound[vertex];
          while (id != -1) {
              removeEdge(id);
              id = nextOutbound[id];
          }
          initInbound();
          id = firstInbound[vertex];
          while (id != -1) {
              removeEdge(id);
              id = nextInbound[id];
          }
      }
  
      private void initInbound() {
          if (firstInbound == null) {
              firstInbound = new int[firstOutbound.length];
              Arrays.fill(firstInbound, 0, vertexCount, -1);
              nextInbound = new int[from.length];
              for (int i = 0; i < edgeCount; i++) {
                  nextInbound[i] = firstInbound[to[i]];
                  firstInbound[to[i]] = 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 removeFlag(int id, int bit) {
          flags[id] &= -1 - (1 << bit);
      }
  
      public final void removeEdge(int id) {
          setFlag(id, REMOVED_BIT);
      }
  
      public final void restoreEdge(int id) {
          removeFlag(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);
              }
          };
      }
  
      public final Iterable<Edge> inbound(final int id) {
          initEdges();
          initInbound();
          return new Iterable<Edge>() {
              public Iterator<Edge> iterator() {
                  return new EdgeIterator(id, firstInbound, nextInbound);
              }
          };
      }
  
      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);
          }
      }
  
      private void ensureVertexCapacity(int size) {
          if (firstOutbound.length < size) {
              int newSize = Math.max(size, 2 * from.length);
              firstOutbound = resize(firstOutbound, newSize);
              if (firstInbound != null) {
                  firstInbound = resize(firstInbound, 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;
      }
  
      public final boolean isSparse() {
          return vertexCount == 0 || edgeCount * 20 / vertexCount <= vertexCount;
      }
  
      protected class GraphEdge implements Edge {
          protected int id;
  
          protected GraphEdge(int id) {
              this.id = id;
          }
  
          public int getSource() {
              return source(id);
          }
  
          public int getDestination() {
              return destination(id);
          }
  
          public long getWeight() {
              return weight(id);
          }
  
          public long getCapacity() {
              return capacity(id);
          }
  
          public long getFlow() {
              return flow(id);
          }
  
          public void pushFlow(long flow) {
              Graph.this.pushFlow(id, flow);
          }
  
          public boolean getFlag(int bit) {
              return flag(id, bit);
          }
  
          public void setFlag(int bit) {
              Graph.this.setFlag(id, bit);
          }
  
          public void removeFlag(int bit) {
              Graph.this.removeFlag(id, bit);
          }
  
          public int getTransposedID() {
              return transposed(id);
          }
  
          public Edge getTransposedEdge() {
              int reverseID = getTransposedID();
              if (reverseID == -1) {
                  return null;
              }
              initEdges();
              return edge(reverseID);
          }
  
          public int getReverseID() {
              return reverse(id);
          }
  
          public Edge getReverseEdge() {
              int reverseID = getReverseID();
              if (reverseID == -1) {
                  return null;
              }
              initEdges();
              return edge(reverseID);
          }
  
          public int getID() {
              return id;
          }
  
          public void remove() {
              removeEdge(id);
          }
  
          public void restore() {
              restoreEdge(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)) {
  