




_UpperCAmelCase		:  Tuple	=   {
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}



def 					UpperCAmelCase__     (   lowerCamelCase,	lowerCamelCase,	lowerCamelCase      ):
  lowercase			:Union[str, Any]							=  set()
  # keep track of all the paths to be checked
  lowercase			:Union[str, Any]							=  [[start]]

  # return path if start is goal
  if start == goal:
    return [start]

  # keeps looping until all possible paths have been checked
  while queue:
    # pop the first path from the queue
    lowercase			:Tuple							=  queue.pop(0      )
    # get the last node from the path
    lowercase			:Any							=  path[-1]
    if node not in explored:
      lowercase			:List[str]							=  graph[node]
      # go through all neighbour nodes, construct a new path and
      # push it into the queue
      for neighbour in neighbours:
        lowercase			:str							=  list(lowerCamelCase      )
        new_path.append(lowerCamelCase      )
        queue.append(lowerCamelCase      )
        # return path if neighbour is goal
        if neighbour == goal:
          return new_path

            # mark node as explored
      explored.add(lowerCamelCase      )

    # in case there's no path between the 2 nodes
  return []



def 					UpperCAmelCase__     (   lowerCamelCase,	lowerCamelCase,	lowerCamelCase      ):
  if not graph or start not in graph or target not in graph:
    return -1
  if start == target:
    return 0
  lowercase			:Union[str, Any]							=  [start]
  lowercase			:Union[str, Any]							=  set(lowerCamelCase      )
  # Keep tab on distances from `start` node.
  lowercase			:Tuple							=  {start: 0, target: -1}
  while queue:
    lowercase			:Optional[Any]							=  queue.pop(0      )
    if node == target:
      lowercase			:Optional[Any]							=  (
          dist[node] if dist[target] == -1 else min(dist[target],	dist[node]      )
      )
    for adjacent in graph[node]:
      if adjacent not in visited:
        visited.add(lowerCamelCase      )
        queue.append(lowerCamelCase      )
        lowercase			:List[Any]							=  dist[node] + 1
  return dist[target]


if __name__ == "__main__":
     print(bfs_shortest_path(demo_graph, "G", "D"))  # returns ['G', 'C', 'A', 'B', 'D']
     print(bfs_shortest_path_distance(demo_graph, "G", "D"))  # returns 4









import itertools
from dataclasses import dataclass
from typing import Optional

import pandas as pd
import pyarrow as pa

import datasets
from datasets.table import table_cast




@dataclass
class       __lowerCAmelCase				(							datasets.BuilderConfig):
       _a           =  None







class       __lowerCAmelCase				(							datasets.ArrowBasedBuilder):
       _a           =  PandasConfig






       def     SCREAMING_SNAKE_CASE			(      self:    Any ):
         return datasets.DatasetInfo(features=self.config.features )






       def     SCREAMING_SNAKE_CASE			(      self:    str				,    _lowerCAmelCase:    List[str] ):
         if not self.config.data_files:
           raise ValueError(F"At least one data file must be specified, but got data_files={self.config.data_files}" )
         lowercase			:int							=  dl_manager.download_and_extract(self.config.data_files )
         if isinstance(_lowerCAmelCase				,    (str, list, tuple) ):
           lowercase			:Union[str, Any]							=  data_files
           if isinstance(_lowerCAmelCase				,    _lowerCAmelCase ):
             lowercase			:str							=  [files]
           # Use `dl_manager.iter_files` to skip hidden files in an extracted archive
           lowercase			:Optional[int]							=  [dl_manager.iter_files(_lowerCAmelCase ) for file in files]
           return [datasets.SplitGenerator(name=datasets.Split.TRAIN				,    gen_kwargs={"files": files} )]
         lowercase			:List[Any]							=  []
         for split_name, files in data_files.items():
           if isinstance(_lowerCAmelCase				,    _lowerCAmelCase ):
             lowercase			:Optional[Any]							=  [files]
           # Use `dl_manager.iter_files` to skip hidden files in an extracted archive
           lowercase			:Optional[Any]							=  [dl_manager.iter_files(_lowerCAmelCase ) for file in files]
           splits.append(datasets.SplitGenerator(name=_lowerCAmelCase				,    gen_kwargs={"files": files} ) )
         return splits






       def     SCREAMING_SNAKE_CASE			(      self:    int				,    _lowerCAmelCase:    pa.Table ):
         if self.config.features is not None:
           # more expensive cast to support nested features with keys in a different order
           # allows str <-> int/float or str to Audio for example
           lowercase			:Any							=  table_cast(_lowerCAmelCase				,    self.config.features.arrow_schema )
         return pa_table






       def     SCREAMING_SNAKE_CASE			(      self:    Optional[int]				,    _lowerCAmelCase:    Union[str, Any] ):
         for i, file in enumerate(itertools.chain.from_iterable(_lowerCAmelCase ) ):
           with open(_lowerCAmelCase				,    "rb" ) as f:
             lowercase			:int							=  pa.Table.from_pandas(pd.read_pickle(_lowerCAmelCase ) )
             yield i, self._cast_table(_lowerCAmelCase )



