

# 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 		_snake_case(       SCREAMING_SNAKE_CASE__     :      Any )				-> int:





    '''simple docstring'''






    A__        =  Queue()
    A__        =  [False] * len(SCREAMING_SNAKE_CASE__ )
    A__        =  [-1] * len(SCREAMING_SNAKE_CASE__ )

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

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

                if color[neighbour] == -1:
                    A__        =  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__ )
            A__        =  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]}))




import unittest

from cer import CER


lowercase_									=    CER()


class 					A		(				unittest.TestCase					):







    """simple docstring"""





    def 		snake_case__	( self					:			str						)->       Dict:





        '''simple docstring'''







        A__        =  ['White House']
        A__        =  ['white house']
        # S = 2, D = 0, I = 0, N = 11, CER = 2 / 11
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.1_818_181_818						) < 1E-6						)


    def 		snake_case__	( self					:			str						)->       Dict:





        '''simple docstring'''







        A__        =  ['were wolf']
        A__        =  ['werewolf']
        # S = 0, D = 0, I = 1, N = 9, CER = 1 / 9
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.1_111_111						) < 1E-6						)

        A__        =  ['werewolf']
        A__        =  ['weae     wolf']
        # S = 1, D = 1, I = 0, N = 8, CER = 0.25
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.25						) < 1E-6						)

        # consecutive whitespaces case 1
        A__        =  ['were wolf']
        A__        =  ['were               wolf']
        # S = 0, D = 0, I = 0, N = 9, CER = 0
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.0						) < 1E-6						)

        # consecutive whitespaces case 2
        A__        =  ['were   wolf']
        A__        =  ['were               wolf']
        # S = 0, D = 0, I = 0, N = 9, CER = 0
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.0						) < 1E-6						)


    def 		snake_case__	( self					:			int						)->       str:





        '''simple docstring'''







        A__        =  ['werewolf']
        A__        =  ['weaewolf']
        # S = 1, D = 0, I = 0, N = 8, CER = 0.125
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.125						) < 1E-6						)


    def 		snake_case__	( self					:			Optional[int]						)->       Optional[int]:





        '''simple docstring'''







        A__        =  ['werewolf']
        A__        =  ['wereawolf']
        # S = 0, D = 1, I = 0, N = 8, CER = 0.125
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.125						) < 1E-6						)


    def 		snake_case__	( self					:			List[Any]						)->       Optional[Any]:





        '''simple docstring'''







        A__        =  ['werewolf']
        A__        =  ['wereolf']
        # S = 0, D = 0, I = 1, N = 8, CER = 0.125
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.125						) < 1E-6						)


    def 		snake_case__	( self					:			str						)->       Tuple:





        '''simple docstring'''







        A__        =  ['werewolf']
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertEqual(lowercase_,0.0						)


    def 		snake_case__	( self					:			Optional[int]						)->       Union[str, Any]:





        '''simple docstring'''







        A__        =  ['werewolf', 'I am your father']
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertEqual(lowercase_,0.0						)

        A__        =  ['werewolf', 'I am your father', 'doge']
        A__        =  ['werxwolf', 'I       am your father', 'doge']
        # S = 1, D = 0, I = 0, N = 28, CER = 1 / 28
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.03_571_428						) < 1E-6						)


    def 		snake_case__	( self					:			List[str]						)->       Union[str, Any]:





        '''simple docstring'''







        A__        =  ['My hovercraft', 'is full of eels']
        A__        =  ['My hovercraft is full', ' of eels']
        # S = 0, D = 0, I = 2, N = 28, CER = 2 / 28
        # whitespace at the front of " of eels" will be strip during preporcessing
        # so need to insert 2 whitespaces
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_,concatenate_texts=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.071_428						) < 1E-6						)


    def 		snake_case__	( self					:			Dict						)->       List[str]:





        '''simple docstring'''







        A__        =  ['我能吞下玻璃而不伤身体']
        A__        =  [' 能吞虾玻璃而 不霜身体啦']
        # S = 3, D = 2, I = 0, N = 11, CER = 5 / 11
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.4_545_454_545						) < 1E-6						)

        A__        =  ['我能吞下玻璃', '而不伤身体']
        A__        =  ['我    能 吞 下 玻 璃', '而不伤身体']
        # S = 0, D = 5, I = 0, N = 11, CER = 5 / 11
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertTrue(abs(char_error_rate - 0.454_545_454_545						) < 1E-6						)

        A__        =  ['我能吞下玻璃而不伤身体']
        A__        =  cer.compute(predictions=lowercase_,references=lowercase_						)
        self.assertFalse(lowercase_,0.0						)


    def 		snake_case__	( self					:			Any						)->       List[str]:





        '''simple docstring'''







        A__        =  ['']
        A__        =  ['Hypothesis']
        with self.assertRaises(lowercase_						):
            cer.compute(predictions=lowercase_,references=lowercase_						)


if __name__ == "__main__":
     unittest.main()

