import java.util.*;

public class Main{

    static int MAX_VERTEXNUM = 100;

    static int [] visited = new int[MAX_VERTEXNUM];

    public static void main(String [] args){

        Graph G = new Graph();

        creatGraph(G);

        output(G);

        for(int i=0;i<G.vertex_num;i++)

            visited[i]=0;

        System.out.println("DFS遍历的结果是：");

        dfs(G,0);//从G.node_list[0]开始DFS遍历

    }

    static void creatGraph(Graph G){

        Scanner in = new Scanner(System.in);

        System.out.println("请输入顶点数v和边数e,（v e）:");

        G.vertex_num = in.nextInt();

        G.edge_num= in.nextInt();

        System.out.println("请输入各顶点信息：");

        for(int i=0;i<G.vertex_num;i++){

            G.node_list[i] = new VertexNode();

            G.node_list[i].date = in.next();

            G.node_list[i].first_edge = null;  //很重要

        }

        System.out.println("请输入各边信息(以空格隔开)：");

        for(int i=0;i<G.edge_num;i++){

            EdgeNode p = new EdgeNode();

            String str1 = in.next();

            String str2 = in.next();

            int v1 = locateVex(G,str1);

            int v2 = locateVex(G,str2);

            p.vertex = v1;

            p.next = G.node_list[v2].first_edge;

            G.node_list[v2].first_edge = p;

            EdgeNode q = new EdgeNode();//如果是有向图，则不存在下面的代码（上面的代码的存储顺序可能有变化）

            q.vertex = v2;

            q.next = G.node_list[v1].first_edge;

            G.node_list[v1].first_edge = q;

        }

    }

    static int locateVex(Graph G,String s){

        for(int i=0;i<G.vertex_num;i++){

            if(G.node_list[i].date.equals(s))

                return i;

        }

        return -1;

    }

    static void output(Graph G){

        System.out.println("输出邻接表存储情况：");

        EdgeNode p = new EdgeNode();

        for(int i=0;i<G.vertex_num;i++){

            System.out.print(G.node_list[i].date);

            p = G.node_list[i].first_edge;

            while(p!=null){

                System.out.print("->"+G.node_list[p.vertex].date);

                p = p.next;

            }

            System.out.println();

        }

    }

    static void dfs(Graph G,int k){

        System.out.println(G.node_list[k].date);

        visited[k]=1;

        EdgeNode p = new EdgeNode();

        p = G.node_list[k].first_edge;

        while(p!=null){

            if(visited[p.vertex]!=1)

                dfs(G,p.vertex);

            p = p.next;

        }

    }

}

//顶点存储

class VertexNode{

    String date;

    EdgeNode first_edge = new EdgeNode();

}

//边存储

class EdgeNode{

    int vertex;

    EdgeNode next;

}

//图存储

class Graph{

    VertexNode [] node_list = new VertexNode[100];

    int vertex_num,edge_num;

}

//输出结果：注意：（邻接表的保存顺序与输入边的顺序有关）