Main.java

import java.util.*;

class ListOfInteger extends ArrayList<Integer> {}

class Graph extends HashMap<Integer,ListOfInteger> {}

public class Main {
  static List discovered = new ListOfInteger();
  static List explored   = new ListOfInteger();

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int x = sc.nextInt();
    int y = sc.nextInt();
    int m = sc.nextInt();

    Graph graph = new Graph();

    for (int i = 1; i <= n; i++)
      graph.put(i, new ListOfInteger());

    for (int i = 0; i < m; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      graph.get(a).add(b);
      graph.get(b).add(a);
    }

    bfs(graph, 1, 3);

    System.out.println(explored);
  }

  static void dfs(Graph g, int v) {
    discovered.add(v);
    g.get(v).forEach(w -> {
      if (!discovered.contains(w))
        dfs(g, w);
    });
  }

  static int bfs(Graph g, int root, int goal) {
    List queue = new ListOfInteger();
    explored.add(root);
    queue.add(root);
    while (!queue.isEmpty()) {
      System.out.println(queue);
      int v = (int)queue.remove(0);
      if (v == goal) {
        System.out.println("gotcha!");
        return v;
      }
      g.get(v).forEach(w -> {
        if (!explored.contains(w)) {
          explored.add(w);
          queue.add(w);
        }
      });
    }
    return -1;
  }
}