import java.util.*;

class Solution {
  /**
   * Find the shortest path between v and u in the graph g.
   *
   * @param g
   *     graph to search in.
   * @param v
   *     node to start from.
   * @param u
   *     node to reach.
   * @return the nodes you that form the shortest path, including v and u. An
   * empty list iff there is no path between v and u.
   */
  public static List<Vertex> shortestPath(Graph g, Vertex v, Vertex u) {
    List<Vertex> slowPath = new ArrayList<>();
    Iterator<Vertex> it = new GraphIterator(g,v);

    while (it.hasNext())
    {
      Vertex x = it.next();

      slowPath.add(x);

      if (x == u)
      {
        break;
      }
    }

    if (slowPath.get(slowPath.size() - 1) != u)
    {
      // Not found
      return new ArrayList<>();
    }

    List<Vertex> fastButReversedPath = new ArrayList<>();
    int i = slowPath.size() - 1;

    while (true)
    {
      Vertex c = slowPath.get(i);
      List<Vertex> connected = g.getNeighbours(c);

      fastButReversedPath.add(c);

      if (c == v)
      {
        Collections.reverse(fastButReversedPath);

        return fastButReversedPath;
      }

      for (Vertex vertex : connected)
      {
        if (fastButReversedPath.contains(vertex))
        {
          continue;
        }

        for (int j = 0; j < i; j++)
        {
          if (slowPath.get(j) == vertex)
          {
            i = j;
          }
        }
      }
    }
  }
}
//