


from multiprocessing import Lock, Pipe, Process

# lock used to ensure that two processes do not access a pipe at the same time
snake_case							:	Union[str, Any]					      =				Lock()






def 							__lowercase       (			__lowerCAmelCase							:    Optional[int] ,   __lowerCAmelCase							:    int ,   __lowerCAmelCase							:    str ,   __lowerCAmelCase							:    Any ,   __lowerCAmelCase							:    Optional[Any] ,   __lowerCAmelCase							:    str ,   __lowerCAmelCase							:    Union[str, Any]       ):
							global process_lock

							# we perform n swaps since after n swaps we know we are sorted
							# we *could* stop early if we are sorted already, but it takes as long to
							# find out we are sorted as it does to sort the list with this algorithm
							for i in range(0 ,   1_0       ):
														if (i + position) % 2 == 0 and r_send is not None:
																					# send your value to your right neighbor
																					process_lock.acquire()
																					r_send[1].send(__lowerCAmelCase       )
																					process_lock.release()

																					# receive your right neighbor's value
																					process_lock.acquire()
																					a__					=					rr_cv[0].recv()
																					process_lock.release()

																					# take the lower value since you are on the left
																					a__					=					min(__lowerCAmelCase ,   __lowerCAmelCase       )
														elif (i + position) % 2 != 0 and l_send is not None:
																					# send your value to your left neighbor
																					process_lock.acquire()
																					l_send[1].send(__lowerCAmelCase       )
																					process_lock.release()

																					# receive your left neighbor's value
																					process_lock.acquire()
																					a__					=					lr_cv[0].recv()
																					process_lock.release()

																					# take the higher value since you are on the right
																					a__					=					max(__lowerCAmelCase ,   __lowerCAmelCase       )
    # after all swaps are performed, send the values back to main
							result_pipe[1].send(__lowerCAmelCase       )






def 							__lowercase       (			__lowerCAmelCase							:    List[str]       ):
							a__					=					[]
							a__					=					[]
							# initialize the list of pipes where the values will be retrieved
							for _ in arr:
														result_pipe.append(Pipe()       )
							# creates the processes
							# the first and last process only have one neighbor so they are made outside
							# of the loop
							a__					=					Pipe()
							a__					=					Pipe()
							process_array_.append(
							    Process(
							        target=__lowerCAmelCase ,   args=(0, arr[0], None, temp_rs, None, temp_rr, result_pipe[0]) ,   )       )
							a__					=					temp_rs
							a__					=					temp_rr

							for i in range(1 ,   len(__lowerCAmelCase       ) - 1       ):
														a__					=					Pipe()
														a__					=					Pipe()
														process_array_.append(
														    Process(
														        target=__lowerCAmelCase ,   args=(i, arr[i], temp_ls, temp_rs, temp_lr, temp_rr, result_pipe[i]) ,   )       )
														a__					=					temp_rs
														a__					=					temp_rr

							process_array_.append(
							    Process(
							        target=__lowerCAmelCase ,   args=(
							            len(__lowerCAmelCase       ) - 1,
							            arr[len(__lowerCAmelCase       ) - 1],
							            temp_ls,
							            None,
							            temp_lr,
							            None,
							            result_pipe[len(__lowerCAmelCase       ) - 1],
							        ) ,   )       )

							# start the processes
							for p in process_array_:
														p.start()

							# wait for the processes to end and write their values to the list
							for p in range(0 ,   len(__lowerCAmelCase       )       ):
														a__					=					result_pipe[p][0].recv()
														process_array_[p].join()
							return arr






def 							__lowercase       (			):
							a__					=					list(range(1_0 ,   0 ,   -1       )       )
							print('Initial List'       )
							print(*__lowerCAmelCase       )
							a__					=					odd_even_transposition(__lowerCAmelCase       )
							print('Sorted List\n'       )
							print(*__lowerCAmelCase       )


if __name__ == "__main__":
						main()








def 							__lowercase       (			__lowerCAmelCase							:    Optional[Any]       ):
							return [
							    {
							        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],
							    },
							    {
							        0: [6],
							        1: [9],
							        2: [4, 5],
							        3: [4],
							        4: [2, 3],
							        5: [2],
							        6: [0, 7],
							        7: [6],
							        8: [],
							        9: [1],
							    },
							    {
							        0: [4],
							        1: [6],
							        2: [],
							        3: [5, 6, 7],
							        4: [0, 6],
							        5: [3, 8, 9],
							        6: [1, 3, 4, 7],
							        7: [3, 6, 8, 9],
							        8: [5, 7],
							        9: [5, 7],
							    },
							    {
							        0: [1, 3],
							        1: [0, 2, 4],
							        2: [1, 3, 4],
							        3: [0, 2, 4],
							        4: [1, 2, 3],
							    },
							][index]






def 							__lowercase       (			__lowerCAmelCase							:    dict[int, list[int]]       ):
							a__					=					0
							a__					=					len(__lowerCAmelCase       )  # No of vertices in graph
							a__					=					[0] * n
							a__					=					[False] * n

							def dfs(__lowerCAmelCase							:    int ,   __lowerCAmelCase							:    Any ,   __lowerCAmelCase							:    Dict ,   __lowerCAmelCase							:    Tuple       ):
														a__					=					True
														a__					=					id_
														id_ += 1
														for to in graph[at]:
																					if to == parent:
																												pass
																					elif not visited[to]:
																												dfs(__lowerCAmelCase ,   __lowerCAmelCase ,   __lowerCAmelCase ,   id_       )
																												a__					=					min(low[at] ,   low[to]       )
																												if id_ <= low[to]:
																																			bridges.append((at, to) if at < to else (to, at)       )
																					else:
																												# This edge is a back edge and cannot be a bridge
																												a__					=					min(low[at] ,   low[to]       )

							a__					=					[]
							for i in range(__lowerCAmelCase       ):
														if not visited[i]:
																					dfs(__lowerCAmelCase ,   -1 ,   __lowerCAmelCase ,   id_       )
							return bridges


if __name__ == "__main__":
						import doctest

						doctest.testmod()




