import java.util.Hashtable;
import java.util.Scanner;
import java.util.Vector;

public class Digraph {

  int n, m;

  Vector<Vector<Integer>> edges;
  Vector<Vector<Integer>> inEdges;
  Hashtable<String, Integer> nameToVertex;
  Vector<String> vertexNames;

  public Digraph(int n) {
    this.n = n;
    nameToVertex = new Hashtable();
    vertexNames = new Vector(n);
    edges = new Vector<Vector<Integer>>();
    inEdges = new Vector<Vector<Integer>>();
    for (int i = 0; i < n; i++) {
      edges.add(new Vector<Integer>());
      inEdges.add(new Vector<Integer>());
    }
  }

  public void addVertex(String name) {
    int u = vertexNames.size();
    vertexNames.add(name);
    nameToVertex.put(name, u);
  }

  public void addEdge(String uName, String vName) {
    if (!nameToVertex.containsKey(uName)) {
      String msg = "vertex " + uName + " not in hashtable";
      throw new RuntimeException(msg);
    }
    if (!nameToVertex.containsKey(vName)) {
      String msg = "vertex " + vName + " not in hashtable";
      throw new RuntimeException(msg);
    }
    int u = nameToVertex.get(uName);
    int v = nameToVertex.get(vName);
    edges.get(u).add(v);
    inEdges.get(v).add(u);
  }

  public static Digraph read(Scanner scanner) {
    Log.print("number of vertices: ");
    int n = scanner.nextInt();
    Log.print("number of edges: ");
    int m = scanner.nextInt();

    Digraph graph = new Digraph(n);

    for (int i = 0; i < n; i++) {
      Log.print("name of vertex " + i + ": ");
      String name = scanner.next();
      Log.println("I read vertex \"" + name + "\"");
      graph.addVertex(name);
    }

    for (int i = 0; i < m; i++) {
      Log.print("enter edge " + (i + 1) + " out of " + m + ": ");
      String uName = scanner.next();
      String vName = scanner.next();
      Log.println("I read edge (" + uName + ", " + vName + ").");
      graph.addEdge(uName, vName);
    }
    return graph;
  }
}