# Path: py_algorithms/graph/adt/edge.py
# class Edge:
#     __slots__ = '_origin', '_destination', '_element'
# 
#     def __init__(self, origin: Vertex, destination: Vertex, element: Any):
#         self._element = element
#         self._destination = destination
#         self._origin = origin
# 
#     def endpoints(self) -> Tuple[Any, Any]:
#         return self._origin, self._destination
# 
#     def opposite(self, v) -> Union[None, Vertex]:
#         return self._destination if v is self._origin else self._origin
# 
#     def element(self) -> Any:
#         return self._element
# 
#     def __hash__(self):
#         return hash((self._origin, self._destination,))
# 
#     def __repr__(self):
#         return "#<{}({}) ({},{})>" \
#             .format(self.__class__.__name__,
#                     self.element(),
#                     self._origin.element(),
#                     self._destination.element())
# 
# Path: py_algorithms/graph/adt/vertex.py
# class Vertex:
#     __slots__ = '_element'
# 
#     def __init__(self, element: Any):
#         self._element = element
# 
#     def element(self) -> Any:
#         return self._element
# 
#     def __hash__(self) -> int:
#         return hash(id(self))
# 
#     def __repr__(self):
#         return "#<{}({})>" \
#             .format(self.__class__.__name__, self.element())


from typing import Any, Iterator
from typing import List
from typing import Set
from typing import Union
from .edge import Edge
from .vertex import Vertex



class Graph:
    def __init__(self, directed: bool = False):
        self._outgoing = {}
        self._incoming = {} if directed else self._outgoing

    def is_directed(self) -> bool:
        return self._incoming is not self._outgoing

    def vertex_count(self) -> int:
        return len(self._outgoing)

    def vertices(self) -> List[Vertex]:
        return list(self._outgoing.keys())

    def edge_count(self) -> int:
        total = sum(len(self._outgoing[v]) for v in self._outgoing)
        return total if self.is_directed() else total // 2

    def edges(self) -> Set[Edge]:
        result = set()
        for sub_map in self._outgoing.values():
            result.update(sub_map.values())
        return result

    def get_edge(self, u, v) -> Union[None, Edge]:
        return self._outgoing[u].get(v)


# Path: py_algorithms/graph/adt/edge.py
# class Edge:
#     __slots__ = '_origin', '_destination', '_element'
# 
#     def __init__(self, origin: Vertex, destination: Vertex, element: Any):
#         self._element = element
#         self._destination = destination
#         self._origin = origin
# 
#     def endpoints(self) -> Tuple[Any, Any]:
#         return self._origin, self._destination
# 
#     def opposite(self, v) -> Union[None, Vertex]:
#         return self._destination if v is self._origin else self._origin
# 
#     def element(self) -> Any:
#         return self._element
# 
#     def __hash__(self):
#         return hash((self._origin, self._destination,))
# 
#     def __repr__(self):
#         return "#<{}({}) ({},{})>" \
#             .format(self.__class__.__name__,
#                     self.element(),
#                     self._origin.element(),
#                     self._destination.element())
# 
# Path: py_algorithms/graph/adt/vertex.py
# class Vertex:
#     __slots__ = '_element'
# 
#     def __init__(self, element: Any):
#         self._element = element
# 
#     def element(self) -> Any:
#         return self._element
# 
#     def __hash__(self) -> int:
#         return hash(id(self))
# 
#     def __repr__(self):
#         return "#<{}({})>" \
#             .format(self.__class__.__name__, self.element())


# Path: py_algorithms/graph/adt/graph.py
from typing import Any, Iterator
from typing import List
from typing import Set
from typing import Union
from .edge import Edge
from .vertex import Vertex




class Graph:
    def __init__(self, directed: bool = False):
        self._outgoing = {}
        self._incoming = {} if directed else self._outgoing

    def is_directed(self) -> bool:
        return self._incoming is not self._outgoing

    def vertex_count(self) -> int:
        return len(self._outgoing)

    def vertices(self) -> List[Vertex]:
        return list(self._outgoing.keys())

    def edge_count(self) -> int:
        total = sum(len(self._outgoing[v]) for v in self._outgoing)
        return total if self.is_directed() else total // 2

    def edges(self) -> Set[Edge]:
        result = set()
        for sub_map in self._outgoing.values():
            result.update(sub_map.values())
        return result

    def get_edge(self, u, v) -> Union[None, Edge]:
        return self._outgoing[u].get(v)


    def degree(self, v: Vertex, outgoing: bool = True) -> int: