

import math


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						int    ):





    """simple docstring"""


    if n <= 0:
        raise ValueError('Only positive integers have prime factors'    )
    SCREAMING_SNAKE_CASE_													=  []
    while n % 2 == 0:
        pf.append(2    )
        SCREAMING_SNAKE_CASE_													=  int(n / 2    )
    for i in range(3	,				int(math.sqrt(_SCREAMING_SNAKE_CASE    )    ) + 1	,				2    ):
        while n % i == 0:
            pf.append(_SCREAMING_SNAKE_CASE    )
            SCREAMING_SNAKE_CASE_													=  int(n / i    )
    if n > 2:
        pf.append(_SCREAMING_SNAKE_CASE    )
    return pf


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						int    ):





    """simple docstring"""


    if n <= 0:
        raise ValueError('Only positive numbers are accepted'    )
    SCREAMING_SNAKE_CASE_													=  1
    SCREAMING_SNAKE_CASE_													=  1
    while n % 2 == 0:
        temp += 1
        SCREAMING_SNAKE_CASE_													=  int(n / 2    )
    div *= temp
    for i in range(3	,				int(math.sqrt(_SCREAMING_SNAKE_CASE    )    ) + 1	,				2    ):
        SCREAMING_SNAKE_CASE_													=  1
        while n % i == 0:
            temp += 1
            SCREAMING_SNAKE_CASE_													=  int(n / i    )
        div *= temp
    if n > 1:
        div *= 2
    return div


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						int    ):





    """simple docstring"""


    if n <= 0:
        raise ValueError('Only positive numbers are accepted'    )
    SCREAMING_SNAKE_CASE_													=  1
    SCREAMING_SNAKE_CASE_													=  1
    while n % 2 == 0:
        temp += 1
        SCREAMING_SNAKE_CASE_													=  int(n / 2    )
    if temp > 1:
        s *= (2**temp - 1) / (2 - 1)
    for i in range(3	,				int(math.sqrt(_SCREAMING_SNAKE_CASE    )    ) + 1	,				2    ):
        SCREAMING_SNAKE_CASE_													=  1
        while n % i == 0:
            temp += 1
            SCREAMING_SNAKE_CASE_													=  int(n / i    )
        if temp > 1:
            s *= (i**temp - 1) / (i - 1)
    return int(_SCREAMING_SNAKE_CASE    )


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						int    ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  n
    for x in set(prime_factors(_SCREAMING_SNAKE_CASE    )    ):
        s *= (x - 1) / x
    return int(_SCREAMING_SNAKE_CASE    )


if __name__ == "__main__":
       import doctest

       doctest.testmod()





# 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]}))


