

from __future__ import annotations


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						int	,				_SCREAMING_SNAKE_CASE   :						Dict	,				_SCREAMING_SNAKE_CASE   :						Tuple    ):





    """simple docstring"""


    assert n > 1 and a > 0 and greatest_common_divisor(lowercase_	,				lowercase_    ) == 1
    ((SCREAMING_SNAKE_CASE_)							,     (SCREAMING_SNAKE_CASE_)							,     (SCREAMING_SNAKE_CASE_))													=  extended_gcd(lowercase_	,				lowercase_    )  # Implemented below
    SCREAMING_SNAKE_CASE_													=  (b * s) % n
    return x


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						int	,				_SCREAMING_SNAKE_CASE   :						Union[str, Any]    ):





    """simple docstring"""


    ((SCREAMING_SNAKE_CASE_)							,     (SCREAMING_SNAKE_CASE_))													=  extended_euclid(lowercase_	,				lowercase_    )  # Implemented below
    if b < 0:
        SCREAMING_SNAKE_CASE_													=  (b % n + n) % n
    return b


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						List[Any]	,				_SCREAMING_SNAKE_CASE   :						Tuple	,				_SCREAMING_SNAKE_CASE   :						int    ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  invert_modulo(lowercase_	,				lowercase_    )
    SCREAMING_SNAKE_CASE_													=  (b * s) % n
    return x


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						Union[str, Any]	,				_SCREAMING_SNAKE_CASE   :						Union[str, Any]    ):





    """simple docstring"""


    assert a >= 0 and b >= 0

    if b == 0:
        SCREAMING_SNAKE_CASE_							,     SCREAMING_SNAKE_CASE_							,     SCREAMING_SNAKE_CASE_													=  a, 1, 0
    else:
        ((SCREAMING_SNAKE_CASE_)							,     (SCREAMING_SNAKE_CASE_)							,     (SCREAMING_SNAKE_CASE_))													=  extended_gcd(lowercase_	,				a % b    )
        SCREAMING_SNAKE_CASE_													=  q
        SCREAMING_SNAKE_CASE_													=  p - q * (a // b)

    assert a % d == 0 and b % d == 0
    assert d == a * x + b * y

    return (d, x, y)


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						Optional[Any]	,				_SCREAMING_SNAKE_CASE   :						str    ):





    """simple docstring"""


    if b == 0:
        return (1, 0)
    ((SCREAMING_SNAKE_CASE_)							,     (SCREAMING_SNAKE_CASE_))													=  extended_euclid(lowercase_	,				a % b    )
    SCREAMING_SNAKE_CASE_													=  a // b
    return (y, x - k * y)


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						Dict	,				_SCREAMING_SNAKE_CASE   :						List[str]    ):





    """simple docstring"""


    if a < b:
        SCREAMING_SNAKE_CASE_							,     SCREAMING_SNAKE_CASE_													=  b, a

    while a % b != 0:
        SCREAMING_SNAKE_CASE_							,     SCREAMING_SNAKE_CASE_													=  b, a % b

    return b


if __name__ == "__main__":
       from doctest import testmod

       testmod(name="modular_division", verbose=True)
       testmod(name="modular_division2", verbose=True)
       testmod(name="invert_modulo", verbose=True)
       testmod(name="extended_gcd", verbose=True)
       testmod(name="extended_euclid", verbose=True)
       testmod(name="greatest_common_divisor", verbose=True)





# A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
# U and V such that every edge (u, v) either connects a vertex from U to V or a vertex
# from V to U. In other words, for every edge (u, v), either u belongs to U and v to V,
# or u belongs to V and v to U. We can also say that there is no edge that connects
# vertices of same set.
from queue import Queue


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						List[str]    ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  Queue()
    SCREAMING_SNAKE_CASE_													=  [False] * len(_SCREAMING_SNAKE_CASE    )
    SCREAMING_SNAKE_CASE_													=  [-1] * len(_SCREAMING_SNAKE_CASE    )

    def bfs():
        while not queue.empty():
            SCREAMING_SNAKE_CASE_													=  queue.get()
            SCREAMING_SNAKE_CASE_													=  True

            for neighbour in graph[u]:
                if neighbour == u:
                    return False

                if color[neighbour] == -1:
                    SCREAMING_SNAKE_CASE_													=  1 - color[u]
                    queue.put(_SCREAMING_SNAKE_CASE    )

                elif color[neighbour] == color[u]:
                    return False

        return True

    for i in range(len(_SCREAMING_SNAKE_CASE    )    ):
        if not visited[i]:
            queue.put(_SCREAMING_SNAKE_CASE    )
            SCREAMING_SNAKE_CASE_													=  0
            if bfs() is False:
                return False

    return True


if __name__ == "__main__":
       # Adjacency List of graph
       print(check_bipartite({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))


