


'''simple docstring'''



def     _UpperCamelCase      (		UpperCamelCase__					):  # noqa: E741
			UpperCAmelCase__  :					List[Any]        =     len(UpperCamelCase__					)
			UpperCAmelCase__  :					Optional[int]        =     0
			UpperCAmelCase__  :					Union[str, Any]        =     [0] * n
			UpperCAmelCase__  :					Dict        =     [False] * n
			UpperCAmelCase__  :					Dict        =     [False] * n

			def dfs(UpperCamelCase__ ,      UpperCamelCase__ ,      UpperCamelCase__ ,      UpperCamelCase__					):
						if parent == root:
									out_edge_count += 1
						UpperCAmelCase__  :					int        =     True
						UpperCAmelCase__  :					Optional[Any]        =     at

						for to in l[at]:
									if to == parent:
												pass
									elif not visited[to]:
												UpperCAmelCase__  :					str        =     dfs(UpperCamelCase__ ,      UpperCamelCase__ ,      UpperCamelCase__ ,      UpperCamelCase__					)
												UpperCAmelCase__  :					Dict        =     min(low[at] ,      low[to]					)

												# AP found via bridge
												if at < low[to]:
															UpperCAmelCase__  :					List[str]        =     True
												# AP found via cycle
												if at == low[to]:
															UpperCAmelCase__  :					Optional[int]        =     True
									else:
												UpperCAmelCase__  :					Dict        =     min(low[at] ,      UpperCamelCase__					)
						return out_edge_count

			for i in range(UpperCamelCase__					):
						if not visited[i]:
									UpperCAmelCase__  :					List[Any]        =     0
									UpperCAmelCase__  :					Union[str, Any]        =     dfs(UpperCamelCase__ ,      UpperCamelCase__ ,      -1 ,      UpperCamelCase__					)
									UpperCAmelCase__  :					Any        =     out_edge_count > 1

			for x in range(len(UpperCamelCase__					)					):
						if is_art[x] is True:
									print(UpperCamelCase__					)


# Adjacency list of graph
__A	={
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3, 5],
    3: [2, 4],
    4: [3],
    5: [2, 6, 8],
    6: [5, 7],
    7: [6, 8],
    8: [5, 7],
}


compute_ap(data)



'''simple docstring'''



import re

from flax.core.frozen_dict import freeze
from flax.traverse_util import flatten_dict, unflatten_dict
from jax.experimental import PartitionSpec as P


# Sentinels
__A	=object()

# For specifying empty leaf dict `{}`
__A	=object()







def     _UpperCamelCase      (		UpperCamelCase__ ,      UpperCamelCase__					):
			UpperCAmelCase__  :					Union[str, Any]        =     tuple((re.compile(x + """$"""					) for x in qs)					)
			for i in range(len(UpperCamelCase__					) - len(UpperCamelCase__					) + 1					):
						UpperCAmelCase__  :					Optional[Any]        =     [x.match(UpperCamelCase__					) for x, y in zip(UpperCamelCase__ ,      ks[i:]					)]
						if matches and all(UpperCamelCase__					):
									return True
			return False







def     _UpperCamelCase      (		UpperCamelCase__					):
			def replace(UpperCamelCase__ ,      UpperCamelCase__					):
						for rule, replacement in rules:
									if _match(UpperCamelCase__ ,      UpperCamelCase__					):
												return replacement
						return val

			return replace







def     _UpperCamelCase      (		):
			return [
			    # embeddings
			    (("transformer", "wpe", "embedding"), P("""mp""" ,      UpperCamelCase__					)),
			    (("transformer", "wte", "embedding"), P("""mp""" ,      UpperCamelCase__					)),
			    # atention
			    (("attention", "(q_proj|k_proj|v_proj)", "kernel"), P(UpperCamelCase__ ,      """mp"""					)),
			    (("attention", "out_proj", "kernel"), P("""mp""" ,      UpperCamelCase__					)),
			    (("attention", "out_proj", "bias"), None),
			    # mlp
			    (("mlp", "c_fc", "kernel"), P(UpperCamelCase__ ,      """mp"""					)),
			    (("mlp", "c_fc", "bias"), P("""mp"""					)),
			    (("mlp", "c_proj", "kernel"), P("""mp""" ,      UpperCamelCase__					)),
			    (("mlp", "c_proj", "bias"), None),
			    # layer norms
			    ((r"ln_\d+", "bias"), None),
			    ((r"\d+", r"ln_\d+", "scale"), None),
			    (("ln_f", "bias"), None),
			    (("ln_f", "scale"), None),
			]







def     _UpperCamelCase      (		UpperCamelCase__					):
			UpperCAmelCase__  :					Optional[int]        =     _get_partition_rules()
			UpperCAmelCase__  :					Optional[int]        =     _replacement_rules(UpperCamelCase__					)
			UpperCAmelCase__  :					List[Any]        =     {k: _unmatched for k in flatten_dict(UpperCamelCase__					)}
			UpperCAmelCase__  :					Tuple        =     {k: replace(UpperCamelCase__ ,      UpperCamelCase__					) for k, v in initd.items()}
			assert _unmatched not in result.values(), "Incomplete partition spec."
			return freeze(unflatten_dict(UpperCamelCase__					)					)