using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

    }

    public class Vertex

    {

        private string _name;

        public string Name

        {

            get { return _name; }

            set { _name = Name; }

        }

        public Vertex(string name)

        {

            _name = name;   

        }

        public override string ToString()

        {

            return _name;   

        }

        public override bool Equals(object obj)

        {

            if(!(obj is Vertex))

                return false;

            return ((Vertex)obj).Name == _name;

        }

        public override int GetHashCode()

        {

            return _name.GetHashCode(); 

        }

    }

    public class Pair<T>

    {

        private T _first;

        private T _last;

        public T First

        {

            get { return _first; }

            set { _first = First; }

        }

        public T Last

        {

            get { return _last; }

            set { _last = Last; }

        }

        public Pair() {}

        public Pair(T first, T last)

        {

            _first = first;

            _last = last;

        }

        public bool Contains(T item)

        {

            if (item.Equals(_first)) return true;

            if (item.Equals(_last)) return true;

            return false;

        }

        public T GetOther(T item)

        {

            if (item.Equals(_first)) return _last;

            if (item.Equals(_last)) return _first;

            return default(T);

        }

    }

    public class Edge

    {

        private Pair<Vertex> _vertices;

        public Pair<Vertex> Vertices

        {

            get { return _vertices; }

            set { _vertices = Vertices; }

        }

        public Edge(Vertex a, Vertex b)

        {

            _vertices = new Pair<Vertex>(a, b);

        }

        public Edge(Pair<string> p)

        {

            _vertices = new Pair<Vertex>(new Vertex(p.First), new Vertex(p.Last));  

        }

        public override string ToString()

        {

            return _vertices.First + " - " + _vertices.Last;    

        }

        public override bool Equals(object obj)

        {

            if(!(obj is Edge))

            {

                return false;

            }

            return (_vertices.First.Equals(obj) && _vertices.Last.Equals(obj));

        }

        public override int GetHashCode()

        {

            return _vertices.First.GetHashCode() * 23 + _vertices.Last.GetHashCode();   

        }

    }

    public class Graph

    {

        private Dictionary<Vertex, bool> _vertices;

        private Dictionary<Edge, bool> _edges;

        public Vertex[] Vertices

        {

            get { return _vertices.Keys.ToArray<Vertex>(); }

        }

        public Edge[] Edges

        {

            get { return _edges.Keys.ToArray<Edge>(); } 

        }

        public Graph()

        {

            _vertices = new Dictionary<Vertex, bool>();

            _edges = new Dictionary<Edge, bool>();

        }   

        public Graph(Vertex[] vertices, Edge[] edges)

        {

            _vertices = new Dictionary<Vertex, bool>();

            _edges = new Dictionary<Edge, bool>();

            foreach(Vertex v in vertices)

            {

                AddNewVertex(v);    

            }

            foreach(Edge e in edges)

            {

                AddNewEdge(e);  

            }

        }

        public Graph(string[]vertices, Edge[] edges)

        {

            _vertices = new Dictionary<Vertex, bool>();

            _edges = new Dictionary<Edge, bool>();

            foreach(string v in vertices)

            {

                AddNewVertex(v);    

            }

            foreach(Edge e in edges)

            {

                AddNewEdge(e);  

            }

        }

        public Graph(Vertex[] vertices, Pair<string> edges)

        {

            _vertices = new Dictionary<Vertex, bool>();

            _edges = new Dictionary<Edge, bool>();

            foreach(Vertex v in vertices)

            {

                AddNewVertex(v);    

            }

            foreach(Pair<string> e in edges)

            {

                AddNewEdge(e);  

            }

        }

        public bool AddNewVertex(Vertex v)

        {

            if(!_vertices.ContainsKey(v))

            {

                _vertices.Add(v, true);

                return true;

            }

            return false;

        }

        public bool AddNewEdge(string a, string b)

        {

            return AddNewEdge(new Pair<string>(a, b));  

        }

        public bool AddNewEdge(Pair<string> p)

        {

            return AddNewEdge(new Edge(p));

        }   

        public bool AddNewEdge(Edge newEdge)

        {

            if(!_edges.ContainsKey(newEdge))

            {

                Vertex firstV = newEdge.Vertices.First;

                Vertex lastV = newEdge.Vertices.Last;

                if (!_vertices.ContainsKey(firstV))

                {

                    AddNewVertex(firstV);   

                }

                if(!_vertices.ContainsKey(lastV))

                {

                    AddNewVertex(lastV);    

                }

                _edges.Add(newEdge, true);

                return true;

            }

            return false;

        }

        public bool RemoveVertex(Vertex vertex)

        {

            if(!_vertices.ContainsKey(vertex))

            {

                return false;   

            }

            foreach(Edge edge in _edges.Keys)

            {

                if(edge.Vertices.Contains(vertex))

                    _edges.Remove(edge);

            }

            _vertices.Remove(vertex);

            return true;

        }

    }

}