
# 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.


def     UpperCAmelCase_  (						__lowerCAmelCase	) ->						Union[str, Any]:
    __lowercase		:			Dict	    =       [False] * len(__lowerCAmelCase	)
    __lowercase		:			int	    =       [-1] * len(__lowerCAmelCase	)

    def dfs(__lowerCAmelCase	,					__lowerCAmelCase	):
        __lowercase		:			Optional[int]	    =       True
        __lowercase		:			Any	    =       c
        for u in graph[v]:
            if not visited[u]:
                dfs(__lowerCAmelCase	,					1 - c	)

    for i in range(len(__lowerCAmelCase	)	):
        if not visited[i]:
            dfs(__lowerCAmelCase	,					0	)

    for i in range(len(__lowerCAmelCase	)	):
        for j in graph[i]:
            if color[i] == color[j]:
                return False

    return True


# Adjacency list of graph
__lowerCAmelCase					:			Tuple			      =		{0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: []}





print(check_bipartite_dfs(graph))




import json
import os
import pickle
import shutil
import tempfile
from unittest import TestCase
from unittest.mock import patch

import numpy as np
from datasets import Dataset

from transformers import is_faiss_available
from transformers.models.bart.configuration_bart import BartConfig
from transformers.models.bart.tokenization_bart import BartTokenizer
from transformers.models.bert.tokenization_bert import VOCAB_FILES_NAMES as DPR_VOCAB_FILES_NAMES
from transformers.models.dpr.configuration_dpr import DPRConfig
from transformers.models.dpr.tokenization_dpr import DPRContextEncoderTokenizer, DPRQuestionEncoderTokenizer
from transformers.models.rag.configuration_rag import RagConfig
from transformers.models.rag.retrieval_rag import CustomHFIndex, RagRetriever
from transformers.models.roberta.tokenization_roberta import VOCAB_FILES_NAMES as BART_VOCAB_FILES_NAMES
from transformers.testing_utils import require_faiss, require_sentencepiece, require_tokenizers, require_torch


if is_faiss_available():
 import faiss


@require_faiss
class 						__lowerCAmelCase	(	lowerCAmelCase_      ):



      """simple docstring"""







      def 		snake_case_			(      self		:       Optional[int]				):
          __lowercase		:			Dict	    =       tempfile.mkdtemp()
          __lowercase		:			Tuple	    =       8

          # DPR tok
          __lowercase		:			Optional[int]	    =       [
              '''[UNK]''',
              '''[CLS]''',
              '''[SEP]''',
              '''[PAD]''',
              '''[MASK]''',
              '''want''',
              '''##want''',
              '''##ed''',
              '''wa''',
              '''un''',
              '''runn''',
              '''##ing''',
              ''',''',
              '''low''',
              '''lowest''',
          ]
          __lowercase		:			Optional[Any]	    =       os.path.join(self.tmpdirname				,       '''dpr_tokenizer'''				)
          os.makedirs(_snake_case				,       exist_ok=_snake_case				)
          __lowercase		:			str	    =       os.path.join(_snake_case				,       DPR_VOCAB_FILES_NAMES['''vocab_file''']				)
          with open(self.vocab_file				,       '''w'''				,       encoding='''utf-8'''				) as vocab_writer:
              vocab_writer.write(''''''.join([x + '''\n''' for x in vocab_tokens]				)				)

          # BART tok
          __lowercase		:			List[str]	    =       [
              '''l''',
              '''o''',
              '''w''',
              '''e''',
              '''r''',
              '''s''',
              '''t''',
              '''i''',
              '''d''',
              '''n''',
              '''\u0120''',
              '''\u0120l''',
              '''\u0120n''',
              '''\u0120lo''',
              '''\u0120low''',
              '''er''',
              '''\u0120lowest''',
              '''\u0120newer''',
              '''\u0120wider''',
              '''<unk>''',
          ]
          __lowercase		:			Optional[Any]	    =       dict(zip(_snake_case				,       range(len(_snake_case				)				)				)				)
          __lowercase		:			int	    =       ['''#version: 0.2''', '''\u0120 l''', '''\u0120l o''', '''\u0120lo w''', '''e r''', '''''']
          __lowercase		:			Any	    =       {'''unk_token''': '''<unk>'''}

          __lowercase		:			int	    =       os.path.join(self.tmpdirname				,       '''bart_tokenizer'''				)
          os.makedirs(_snake_case				,       exist_ok=_snake_case				)
          __lowercase		:			List[Any]	    =       os.path.join(_snake_case				,       BART_VOCAB_FILES_NAMES['''vocab_file''']				)
          __lowercase		:			Tuple	    =       os.path.join(_snake_case				,       BART_VOCAB_FILES_NAMES['''merges_file''']				)
          with open(self.vocab_file				,       '''w'''				,       encoding='''utf-8'''				) as fp:
              fp.write(json.dumps(_snake_case				) + '''\n'''				)
          with open(self.merges_file				,       '''w'''				,       encoding='''utf-8'''				) as fp:
              fp.write('''\n'''.join(_snake_case				)				)




      def 		snake_case_			(      self		:       List[Any]				):
          return DPRQuestionEncoderTokenizer.from_pretrained(os.path.join(self.tmpdirname				,       '''dpr_tokenizer'''				)				)




      def 		snake_case_			(      self		:       Dict				):
          return DPRContextEncoderTokenizer.from_pretrained(os.path.join(self.tmpdirname				,       '''dpr_tokenizer'''				)				)




      def 		snake_case_			(      self		:       Optional[int]				):
          return BartTokenizer.from_pretrained(os.path.join(self.tmpdirname				,       '''bart_tokenizer'''				)				)




      def 		snake_case_			(      self		:       str				):
          shutil.rmtree(self.tmpdirname				)




      def 		snake_case_			(      self		:       Tuple				):
          __lowercase		:			Dict	    =       Dataset.from_dict(
              {
                  '''id''': ['''0''', '''1'''],
                  '''text''': ['''foo''', '''bar'''],
                  '''title''': ['''Foo''', '''Bar'''],
                  '''embeddings''': [np.ones(self.retrieval_vector_size				), 2 * np.ones(self.retrieval_vector_size				)],
              }				)
          dataset.add_faiss_index('''embeddings'''				,       string_factory='''Flat'''				,       metric_type=faiss.METRIC_INNER_PRODUCT				)
          return dataset




      def 		snake_case_			(      self		:       Union[str, Any]				):
          __lowercase		:			Union[str, Any]	    =       self.get_dummy_dataset()
          __lowercase		:			Optional[int]	    =       RagConfig(
              retrieval_vector_size=self.retrieval_vector_size				,       question_encoder=DPRConfig().to_dict()				,       generator=BartConfig().to_dict()				,       )
          with patch('''transformers.models.rag.retrieval_rag.load_dataset'''				) as mock_load_dataset:
              __lowercase		:			List[Any]	    =       dataset
              __lowercase		:			str	    =       RagRetriever(
                  _snake_case				,       question_encoder_tokenizer=self.get_dpr_tokenizer()				,       generator_tokenizer=self.get_bart_tokenizer()				,       )
          return retriever




      def 		snake_case_			(      self		:       int				,       _snake_case		:       bool				):
          __lowercase		:			Dict	    =       self.get_dummy_dataset()
          __lowercase		:			List[Any]	    =       RagConfig(
              retrieval_vector_size=self.retrieval_vector_size				,       question_encoder=DPRConfig().to_dict()				,       generator=BartConfig().to_dict()				,       index_name='''custom'''				,       )
          if from_disk:
              __lowercase		:			List[Any]	    =       os.path.join(self.tmpdirname				,       '''dataset'''				)
              __lowercase		:			Union[str, Any]	    =       os.path.join(self.tmpdirname				,       '''index.faiss'''				)
              dataset.get_index('''embeddings'''				).save(os.path.join(self.tmpdirname				,       '''index.faiss'''				)				)
              dataset.drop_index('''embeddings'''				)
              dataset.save_to_disk(os.path.join(self.tmpdirname				,       '''dataset'''				)				)
              del dataset
              __lowercase		:			Optional[Any]	    =       RagRetriever(
                  _snake_case				,       question_encoder_tokenizer=self.get_dpr_tokenizer()				,       generator_tokenizer=self.get_bart_tokenizer()				,       )
          else:
              __lowercase		:			Optional[Any]	    =       RagRetriever(
                  _snake_case				,       question_encoder_tokenizer=self.get_dpr_tokenizer()				,       generator_tokenizer=self.get_bart_tokenizer()				,       index=CustomHFIndex(config.retrieval_vector_size				,       _snake_case				)				,       )
          return retriever




      def 		snake_case_			(      self		:       str				):
          __lowercase		:			List[str]	    =       Dataset.from_dict(
              {
                  '''id''': ['''0''', '''1'''],
                  '''text''': ['''foo''', '''bar'''],
                  '''title''': ['''Foo''', '''Bar'''],
                  '''embeddings''': [np.ones(self.retrieval_vector_size + 1				), 2 * np.ones(self.retrieval_vector_size + 1				)],
              }				)
          dataset.add_faiss_index('''embeddings'''				,       string_factory='''Flat'''				,       metric_type=faiss.METRIC_INNER_PRODUCT				)

          __lowercase		:			Optional[int]	    =       os.path.join(self.tmpdirname				,       '''hf_bert_base.hnswSQ8_correct_phi_128.c_index'''				)
          dataset.save_faiss_index('''embeddings'''				,       index_file_name + '''.index.dpr'''				)
          pickle.dump(dataset['''id''']				,       open(index_file_name + '''.index_meta.dpr'''				,       '''wb'''				)				)

          __lowercase		:			str	    =       os.path.join(self.tmpdirname				,       '''psgs_w100.tsv.pkl'''				)
          __lowercase		:			Dict	    =       {sample['''id''']: [sample['''text'''], sample['''title''']] for sample in dataset}
          pickle.dump(_snake_case				,       open(_snake_case				,       '''wb'''				)				)

          __lowercase		:			List[str]	    =       RagConfig(
              retrieval_vector_size=self.retrieval_vector_size				,       question_encoder=DPRConfig().to_dict()				,       generator=BartConfig().to_dict()				,       index_name='''legacy'''				,       index_path=self.tmpdirname				,       )
          __lowercase		:			Optional[int]	    =       RagRetriever(
              _snake_case				,       question_encoder_tokenizer=self.get_dpr_tokenizer()				,       generator_tokenizer=self.get_bart_tokenizer()				)
          return retriever




      def 		snake_case_			(      self		:       Optional[Any]				):
          __lowercase		:			List[str]	    =       1
          __lowercase		:			Tuple	    =       self.get_dummy_canonical_hf_index_retriever()
          __lowercase		:			List[Any]	    =       np.array(
              [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
          __lowercase    ,      __lowercase    ,      __lowercase		:			str	    =       retriever.retrieve(_snake_case				,       n_docs=_snake_case				)
          self.assertEqual(retrieved_doc_embeds.shape				,       (2, n_docs, self.retrieval_vector_size)				)
          self.assertEqual(len(_snake_case				)				,       2				)
          self.assertEqual(sorted(doc_dicts[0]				)				,       ['''embeddings''', '''id''', '''text''', '''title''']				)
          self.assertEqual(len(doc_dicts[0]['''id''']				)				,       _snake_case				)
          self.assertEqual(doc_dicts[0]['''id'''][0]				,       '''1'''				)  # max inner product is reached with second doc
          self.assertEqual(doc_dicts[1]['''id'''][0]				,       '''0'''				)  # max inner product is reached with first doc
          self.assertListEqual(doc_ids.tolist()				,       [[1], [0]]				)




      def 		snake_case_			(      self		:       int				):
          __lowercase		:			int	    =       self.get_dummy_canonical_hf_index_retriever()
          with tempfile.TemporaryDirectory() as tmp_dirname:
              with patch('''transformers.models.rag.retrieval_rag.load_dataset'''				) as mock_load_dataset:
                  __lowercase		:			Optional[Any]	    =       self.get_dummy_dataset()
                  retriever.save_pretrained(_snake_case				)
                  __lowercase		:			str	    =       RagRetriever.from_pretrained(_snake_case				)
                  self.assertIsInstance(_snake_case				,       _snake_case				)
                  __lowercase		:			List[str]	    =       np.array(
                      [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
                  __lowercase		:			Union[str, Any]	    =       retriever.retrieve(_snake_case				,       n_docs=1				)
                  self.assertTrue(out is not None				)




      def 		snake_case_			(      self		:       str				):
          __lowercase		:			List[str]	    =       1
          __lowercase		:			Dict	    =       self.get_dummy_custom_hf_index_retriever(from_disk=_snake_case				)
          __lowercase		:			Optional[Any]	    =       np.array(
              [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
          __lowercase    ,      __lowercase    ,      __lowercase		:			Tuple	    =       retriever.retrieve(_snake_case				,       n_docs=_snake_case				)
          self.assertEqual(retrieved_doc_embeds.shape				,       (2, n_docs, self.retrieval_vector_size)				)
          self.assertEqual(len(_snake_case				)				,       2				)
          self.assertEqual(sorted(doc_dicts[0]				)				,       ['''embeddings''', '''id''', '''text''', '''title''']				)
          self.assertEqual(len(doc_dicts[0]['''id''']				)				,       _snake_case				)
          self.assertEqual(doc_dicts[0]['''id'''][0]				,       '''1'''				)  # max inner product is reached with second doc
          self.assertEqual(doc_dicts[1]['''id'''][0]				,       '''0'''				)  # max inner product is reached with first doc
          self.assertListEqual(doc_ids.tolist()				,       [[1], [0]]				)




      def 		snake_case_			(      self		:       Any				):
          __lowercase		:			List[str]	    =       self.get_dummy_custom_hf_index_retriever(from_disk=_snake_case				)
          with tempfile.TemporaryDirectory() as tmp_dirname:
              retriever.save_pretrained(_snake_case				)
              __lowercase		:			Optional[Any]	    =       RagRetriever.from_pretrained(_snake_case				)
              self.assertIsInstance(_snake_case				,       _snake_case				)
              __lowercase		:			Optional[Any]	    =       np.array(
                  [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
              __lowercase		:			List[Any]	    =       retriever.retrieve(_snake_case				,       n_docs=1				)
              self.assertTrue(out is not None				)




      def 		snake_case_			(      self		:       List[Any]				):
          __lowercase		:			Any	    =       1
          __lowercase		:			List[Any]	    =       self.get_dummy_custom_hf_index_retriever(from_disk=_snake_case				)
          __lowercase		:			Any	    =       np.array(
              [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
          __lowercase    ,      __lowercase    ,      __lowercase		:			Union[str, Any]	    =       retriever.retrieve(_snake_case				,       n_docs=_snake_case				)
          self.assertEqual(retrieved_doc_embeds.shape				,       (2, n_docs, self.retrieval_vector_size)				)
          self.assertEqual(len(_snake_case				)				,       2				)
          self.assertEqual(sorted(doc_dicts[0]				)				,       ['''embeddings''', '''id''', '''text''', '''title''']				)
          self.assertEqual(len(doc_dicts[0]['''id''']				)				,       _snake_case				)
          self.assertEqual(doc_dicts[0]['''id'''][0]				,       '''1'''				)  # max inner product is reached with second doc
          self.assertEqual(doc_dicts[1]['''id'''][0]				,       '''0'''				)  # max inner product is reached with first doc
          self.assertListEqual(doc_ids.tolist()				,       [[1], [0]]				)




      def 		snake_case_			(      self		:       Any				):
          __lowercase		:			str	    =       self.get_dummy_custom_hf_index_retriever(from_disk=_snake_case				)
          with tempfile.TemporaryDirectory() as tmp_dirname:
              retriever.save_pretrained(_snake_case				)
              __lowercase		:			Optional[int]	    =       RagRetriever.from_pretrained(_snake_case				)
              self.assertIsInstance(_snake_case				,       _snake_case				)
              __lowercase		:			Union[str, Any]	    =       np.array(
                  [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
              __lowercase		:			Tuple	    =       retriever.retrieve(_snake_case				,       n_docs=1				)
              self.assertTrue(out is not None				)




      def 		snake_case_			(      self		:       Tuple				):
          __lowercase		:			Optional[int]	    =       1
          __lowercase		:			str	    =       self.get_dummy_legacy_index_retriever()
          __lowercase		:			Tuple	    =       np.array(
              [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
          __lowercase    ,      __lowercase    ,      __lowercase		:			Tuple	    =       retriever.retrieve(_snake_case				,       n_docs=_snake_case				)
          self.assertEqual(retrieved_doc_embeds.shape				,       (2, n_docs, self.retrieval_vector_size)				)
          self.assertEqual(len(_snake_case				)				,       2				)
          self.assertEqual(sorted(doc_dicts[0]				)				,       ['''text''', '''title''']				)
          self.assertEqual(len(doc_dicts[0]['''text''']				)				,       _snake_case				)
          self.assertEqual(doc_dicts[0]['''text'''][0]				,       '''bar'''				)  # max inner product is reached with second doc
          self.assertEqual(doc_dicts[1]['''text'''][0]				,       '''foo'''				)  # max inner product is reached with first doc
          self.assertListEqual(doc_ids.tolist()				,       [[1], [0]]				)




      def 		snake_case_			(      self		:       Union[str, Any]				):
          __lowercase		:			Tuple	    =       self.get_dummy_legacy_index_retriever()
          with tempfile.TemporaryDirectory() as tmp_dirname:
              retriever.save_pretrained(_snake_case				)
              __lowercase		:			Tuple	    =       RagRetriever.from_pretrained(_snake_case				)
              self.assertIsInstance(_snake_case				,       _snake_case				)
              __lowercase		:			Optional[int]	    =       np.array(
                  [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
              __lowercase		:			Tuple	    =       retriever.retrieve(_snake_case				,       n_docs=1				)
              self.assertTrue(out is not None				)




      @require_torch
      @require_tokenizers
      @require_sentencepiece
      def 		snake_case_			(      self		:       Optional[Any]				):
          import torch

          __lowercase		:			Tuple	    =       1
          __lowercase		:			Any	    =       self.get_dummy_canonical_hf_index_retriever()
          __lowercase		:			str	    =       [[5, 7], [10, 11]]
          __lowercase		:			List[Any]	    =       np.array(
              [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
          __lowercase		:			Any	    =       retriever(_snake_case				,       _snake_case				,       prefix=retriever.config.generator.prefix				,       n_docs=_snake_case				)
          __lowercase    ,      __lowercase    ,      __lowercase		:			Tuple	    =       (
              out['''context_input_ids'''],
              out['''context_attention_mask'''],
              out['''retrieved_doc_embeds'''],
          )
          self.assertEqual(retrieved_doc_embeds.shape				,       (2, n_docs, self.retrieval_vector_size)				)
          self.assertIsInstance(_snake_case				,       _snake_case				)
          self.assertIsInstance(_snake_case				,       _snake_case				)
          self.assertIsInstance(_snake_case				,       np.ndarray				)

          __lowercase		:			Optional[Any]	    =       retriever(
              _snake_case				,       _snake_case				,       prefix=retriever.config.generator.prefix				,       n_docs=_snake_case				,       return_tensors='''pt'''				,       )
          __lowercase    ,      __lowercase    ,      __lowercase    ,      __lowercase		:			Optional[Any]	    =       (  # noqa: F841
              out['''context_input_ids'''],
              out['''context_attention_mask'''],
              out['''retrieved_doc_embeds'''],
              out['''doc_ids'''],
          )
          self.assertEqual(retrieved_doc_embeds.shape				,       (2, n_docs, self.retrieval_vector_size)				)
          self.assertIsInstance(_snake_case				,       torch.Tensor				)
          self.assertIsInstance(_snake_case				,       torch.Tensor				)
          self.assertIsInstance(_snake_case				,       torch.Tensor				)




      @require_torch
      @require_tokenizers
      @require_sentencepiece
      def 		snake_case_			(      self		:       List[Any]				):
          __lowercase		:			Tuple	    =       self.get_dpr_ctx_encoder_tokenizer()
          __lowercase		:			str	    =       1
          __lowercase		:			int	    =       self.get_dummy_custom_hf_index_retriever(from_disk=_snake_case				)
          retriever.set_ctx_encoder_tokenizer(_snake_case				)

          __lowercase		:			Tuple	    =       [[5, 7], [10, 11]]
          __lowercase		:			int	    =       np.array(
              [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,       dtype=np.floataa				)
          __lowercase		:			Any	    =       retriever(_snake_case				,       _snake_case				,       prefix=retriever.config.generator.prefix				,       n_docs=_snake_case				)

          self.assertEqual(
              len(_snake_case				)				,       6				)  # check whether the retriever output consist of 6 attributes including tokenized docs
          self.assertEqual(
              all(k in out for k in ('''tokenized_doc_ids''', '''tokenized_doc_attention_mask''')				)				,       _snake_case				)  # check for doc token related keys in dictionary.


