
from collections import deque







def 				UpperCAmelCase_(    a__   ):



    """simple docstring"""



    return input(a__   ).strip().split(''' '''   )







def 				UpperCAmelCase_(    a__ ,						a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				dict[int, list[int]]				      = {}
    for i in range(a__   ):
        SCREAMING_SNAKE_CASE				:				Union[str, Any]				      = []

    for e in range(a__   ):
        SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE				:				Dict				      = (int(a__   ) for i in _input(F"""Edge {e + 1}: <node1> <node2> """   ))
        graph[x].append(a__   )
    return graph







def 				UpperCAmelCase_(    a__ ,						a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				dict[int, list[int]]				      = {}
    for i in range(a__   ):
        SCREAMING_SNAKE_CASE				:				Dict				      = []

    for e in range(a__   ):
        SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE				:				int				      = (int(a__   ) for i in _input(F"""Edge {e + 1}: <node1> <node2> """   ))
        graph[x].append(a__   )
        graph[y].append(a__   )
    return graph







def 				UpperCAmelCase_(    a__ ,						a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				dict[int, list[tuple[int, int]]]				      = {}
    for i in range(a__   ):
        SCREAMING_SNAKE_CASE				:				Union[str, Any]				      = []

    for e in range(a__   ):
        SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE				:				Optional[Any]				      = (int(a__   ) for i in _input(F"""Edge {e + 1}: <node1> <node2> <weight> """   ))
        graph[x].append((y, w)   )
        graph[y].append((x, w)   )
    return graph


if __name__ == "__main__":
      a__		,    a__				:      Any    		=     (int(i) for i in _input('''Number of nodes and edges: '''))

      a__				:      Optional[Any]    		=     int(
          _input(
              '''Press 1 or 2 or 3 \n'''
              '''1. Unweighted directed \n'''
              '''2. Unweighted undirected \n'''
              '''3. Weighted undirected \n'''
          )[0]
      )

      a__				:      Optional[int]    		=     {
          1: initialize_unweighted_directed_graph,
          2: initialize_unweighted_undirected_graph,
          3: initialize_weighted_undirected_graph,
      }[graph_choice](n, m)







def 				UpperCAmelCase_(    a__ ,						a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE				:				List[str]				      = {s}, [s]
    print(a__   )
    while _s:
        SCREAMING_SNAKE_CASE				:				List[Any]				      = 0
        for i in g[_s[-1]]:
            if i not in vis:
                _s.append(a__   )
                vis.add(a__   )
                SCREAMING_SNAKE_CASE				:				int				      = 1
                print(a__   )
                break
        if not flag:
            _s.pop()







def 				UpperCAmelCase_(    a__ ,						a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE				:				Dict				      = {s}, deque([s]   )
    print(a__   )
    while q:
        SCREAMING_SNAKE_CASE				:				str				      = q.popleft()
        for v in g[u]:
            if v not in vis:
                vis.add(a__   )
                q.append(a__   )
                print(a__   )







def 				UpperCAmelCase_(    a__ ,						a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE				:				List[Any]				      = {s: 0}, set(), {s: 0}
    while True:
        if len(a__   ) == len(a__   ) - 1:
            break
        SCREAMING_SNAKE_CASE				:				Optional[Any]				      = 100_000
        for i in dist:
            if i not in known and dist[i] < mini:
                SCREAMING_SNAKE_CASE				:				Any				      = dist[i]
                SCREAMING_SNAKE_CASE				:				Union[str, Any]				      = i
        known.add(a__   )
        for v in g[u]:
            if v[0] not in known and dist[u] + v[1] < dist.get(v[0] ,						100_000   ):
                SCREAMING_SNAKE_CASE				:				List[str]				      = dist[u] + v[1]
                SCREAMING_SNAKE_CASE				:				Any				      = u
    for i in dist:
        if i != s:
            print(dist[i]   )







def 				UpperCAmelCase_(    a__ ,						a__=None ,						a__=None   ):



    """simple docstring"""



    if q is None:
        SCREAMING_SNAKE_CASE				:				str				      = [1]
    if ind is None:
        SCREAMING_SNAKE_CASE				:				Tuple				      = [0] * (len(a__   ) + 1)  # SInce oth Index is ignored
        for u in g:
            for v in g[u]:
                ind[v] += 1
        SCREAMING_SNAKE_CASE				:				Any				      = deque()
        for i in g:
            if ind[i] == 0:
                q.append(a__   )
    if len(a__   ) == 0:
        return
    SCREAMING_SNAKE_CASE				:				Dict				      = q.popleft()
    print(a__   )
    for w in g[v]:
        ind[w] -= 1
        if ind[w] == 0:
            q.append(a__   )
    topo(a__ ,						a__ ,						a__   )







def 				UpperCAmelCase_(    ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				Optional[int]				      = input().strip()
    SCREAMING_SNAKE_CASE				:				Optional[int]				      = []
    for _ in range(a__   ):
        a.append(map(a__ ,						input().strip().split()   )   )
    return a, n







def 				UpperCAmelCase_(    a__   ):



    """simple docstring"""



    ((SCREAMING_SNAKE_CASE)      ,							(SCREAMING_SNAKE_CASE))				:				Optional[int]				      = a_and_n
    SCREAMING_SNAKE_CASE				:				Any				      = list(a__   )
    SCREAMING_SNAKE_CASE				:				List[Any]				      = [[0] * n for i in range(a__   )]
    for k in range(a__   ):
        for i in range(a__   ):
            for j in range(a__   ):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    SCREAMING_SNAKE_CASE				:				Tuple				      = dist[i][k] + dist[k][j]
                    SCREAMING_SNAKE_CASE				:				Optional[int]				      = k
    print(a__   )







def 				UpperCAmelCase_(    a__ ,						a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE				:				Optional[int]				      = {s: 0}, set(), {s: 0}
    while True:
        if len(a__   ) == len(a__   ) - 1:
            break
        SCREAMING_SNAKE_CASE				:				str				      = 100_000
        for i in dist:
            if i not in known and dist[i] < mini:
                SCREAMING_SNAKE_CASE				:				Dict				      = dist[i]
                SCREAMING_SNAKE_CASE				:				int				      = i
        known.add(a__   )
        for v in g[u]:
            if v[0] not in known and v[1] < dist.get(v[0] ,						100_000   ):
                SCREAMING_SNAKE_CASE				:				List[str]				      = v[1]
                SCREAMING_SNAKE_CASE				:				Union[str, Any]				      = u
    return dist







def 				UpperCAmelCase_(    ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE      ,							SCREAMING_SNAKE_CASE				:				Tuple				      = map(a__ ,						input().split(''' '''   )   )
    SCREAMING_SNAKE_CASE				:				Union[str, Any]				      = []
    for _ in range(a__   ):
        edges.append(map(a__ ,						input().split(''' '''   )   )   )
    return edges, n







def 				UpperCAmelCase_(    a__   ):



    """simple docstring"""



    ((SCREAMING_SNAKE_CASE)      ,							(SCREAMING_SNAKE_CASE))				:				Any				      = e_and_n
    e.sort(reverse=a__ ,						key=lambda a__   : x[2]   )
    SCREAMING_SNAKE_CASE				:				Union[str, Any]				      = [{i} for i in range(1 ,						n + 1   )]
    while True:
        if len(a__   ) == 1:
            break
        print(a__   )
        SCREAMING_SNAKE_CASE				:				str				      = e.pop()
        for i in range(len(a__   )   ):
            if x[0] in s[i]:
                break
        for j in range(len(a__   )   ):
            if x[1] in s[j]:
                if i == j:
                    break
                s[j].update(s[i]   )
                s.pop(a__   )
                break







def 				UpperCAmelCase_(    a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				Union[str, Any]				      = []
    for node in graph:
        if not graph[node]:
            isolated.append(a__   )
    return isolated


import inspect
from typing import Callable, List, Optional, Set, Tuple, Union

import torch
from packaging import version
from safetensors.torch import storage_ptr, storage_size
from torch import nn

from .utils import logging


a__				:      Tuple    		=     [nn.LayerNorm]

a__				:      Tuple    		=     logging.get_logger(__name__)

a__				:      int    		=     version.parse(version.parse(torch.__version__).base_version)

a__				:      Dict    		=     parsed_torch_version_base >= version.parse('''2.0''')
a__				:      Any    		=     parsed_torch_version_base >= version.parse('''1.12''')
a__				:      Union[str, Any]    		=     parsed_torch_version_base >= version.parse('''1.11''')
a__				:      Union[str, Any]    		=     parsed_torch_version_base < version.parse('''1.11''')







def 				UpperCAmelCase_(    a__ ,						a__ ,						a__ ,						a__ ,						self   ):



    """simple docstring"""



    from torch import _softmax_backward_data

    if is_torch_less_than_1_11:
        return _softmax_backward_data(a__ ,						a__ ,						parent.dim ,						self   )
    else:
        return _softmax_backward_data(a__ ,						a__ ,						parent.dim ,						self.dtype   )







def 				UpperCAmelCase_(    a__ ,						a__ ,						a__ = 0   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				Optional[Any]				      = index.to(layer.weight.device   )
    SCREAMING_SNAKE_CASE				:				Optional[Any]				      = layer.weight.index_select(a__ ,						a__   ).clone().detach()
    if layer.bias is not None:
        if dim == 1:
            SCREAMING_SNAKE_CASE				:				int				      = layer.bias.clone().detach()
        else:
            SCREAMING_SNAKE_CASE				:				List[Any]				      = layer.bias[index].clone().detach()
    SCREAMING_SNAKE_CASE				:				List[Any]				      = list(layer.weight.size()   )
    SCREAMING_SNAKE_CASE				:				List[Any]				      = len(a__   )
    SCREAMING_SNAKE_CASE				:				str				      = nn.Linear(new_size[1] ,						new_size[0] ,						bias=layer.bias is not None   ).to(layer.weight.device   )
    SCREAMING_SNAKE_CASE				:				Optional[Any]				      = False
    new_layer.weight.copy_(W.contiguous()   )
    SCREAMING_SNAKE_CASE				:				Tuple				      = True
    if layer.bias is not None:
        SCREAMING_SNAKE_CASE				:				Dict				      = False
        new_layer.bias.copy_(b.contiguous()   )
        SCREAMING_SNAKE_CASE				:				Tuple				      = True
    return new_layer






class     a_       (			nn.Module							):



       """simple docstring"""






       def __init__(		self				,       _lowerCamelCase				,       _lowerCamelCase   )					->int:
           super().__init__()
           SCREAMING_SNAKE_CASE				:				List[str]				      = nf
           SCREAMING_SNAKE_CASE				:				List[Any]				      = nn.Parameter(torch.empty(_lowerCamelCase				,       _lowerCamelCase   )   )
           SCREAMING_SNAKE_CASE				:				Tuple				      = nn.Parameter(torch.zeros(_lowerCamelCase   )   )
           nn.init.normal_(self.weight				,       std=0.0_2   )






       def 	__lowerCAmelCase     (		self				,       _lowerCamelCase   )					->Tuple:
           SCREAMING_SNAKE_CASE				:				Optional[Any]				      = x.size()[:-1] + (self.nf,)
           SCREAMING_SNAKE_CASE				:				int				      = torch.addmm(self.bias				,       x.view(-1				,       x.size(-1   )   )				,       self.weight   )
           SCREAMING_SNAKE_CASE				:				Tuple				      = x.view(_lowerCamelCase   )
           return x







def 				UpperCAmelCase_(    a__ ,						a__ ,						a__ = 1   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				str				      = index.to(layer.weight.device   )
    SCREAMING_SNAKE_CASE				:				Any				      = layer.weight.index_select(a__ ,						a__   ).clone().detach()
    if dim == 0:
        SCREAMING_SNAKE_CASE				:				Tuple				      = layer.bias.clone().detach()
    else:
        SCREAMING_SNAKE_CASE				:				Optional[int]				      = layer.bias[index].clone().detach()
    SCREAMING_SNAKE_CASE				:				int				      = list(layer.weight.size()   )
    SCREAMING_SNAKE_CASE				:				Tuple				      = len(a__   )
    SCREAMING_SNAKE_CASE				:				Any				      = ConvaD(new_size[1] ,						new_size[0]   ).to(layer.weight.device   )
    SCREAMING_SNAKE_CASE				:				Optional[int]				      = False
    new_layer.weight.copy_(W.contiguous()   )
    SCREAMING_SNAKE_CASE				:				int				      = True
    SCREAMING_SNAKE_CASE				:				Any				      = False
    new_layer.bias.copy_(b.contiguous()   )
    SCREAMING_SNAKE_CASE				:				int				      = True
    return new_layer







def 				UpperCAmelCase_(    a__ ,						a__ ,						a__ = None   ):



    """simple docstring"""



    if isinstance(a__ ,						nn.Linear   ):
        return prune_linear_layer(a__ ,						a__ ,						dim=0 if dim is None else dim   )
    elif isinstance(a__ ,						a__   ):
        return prune_convad_layer(a__ ,						a__ ,						dim=1 if dim is None else dim   )
    else:
        raise ValueError(F"""Can't prune layer of class {layer.__class__}"""   )







def 				UpperCAmelCase_(    a__ ,						a__ ,						a__ ,						*a__   ):



    """simple docstring"""



    assert len(a__   ) > 0, F"""{input_tensors} has to be a tuple/list of tensors"""

    # inspect.signature exist since python 3.5 and is a python method -> no problem with backward compatibility
    SCREAMING_SNAKE_CASE				:				str				      = len(inspect.signature(a__   ).parameters   )
    if num_args_in_forward_chunk_fn != len(a__   ):
        raise ValueError(
            F"""forward_chunk_fn expects {num_args_in_forward_chunk_fn} arguments, but only {len(a__   )} input """
            '''tensors are given'''   )

    if chunk_size > 0:
        SCREAMING_SNAKE_CASE				:				Dict				      = input_tensors[0].shape[chunk_dim]
        for input_tensor in input_tensors:
            if input_tensor.shape[chunk_dim] != tensor_shape:
                raise ValueError(
                    F"""All input tenors have to be of the same shape: {tensor_shape}, """
                    F"""found shape {input_tensor.shape[chunk_dim]}"""   )

        if input_tensors[0].shape[chunk_dim] % chunk_size != 0:
            raise ValueError(
                F"""The dimension to be chunked {input_tensors[0].shape[chunk_dim]} has to be a multiple of the chunk """
                F"""size {chunk_size}"""   )

        SCREAMING_SNAKE_CASE				:				Any				      = input_tensors[0].shape[chunk_dim] // chunk_size

        # chunk input tensor into tuples
        SCREAMING_SNAKE_CASE				:				Optional[int]				      = tuple(input_tensor.chunk(a__ ,						dim=a__   ) for input_tensor in input_tensors   )
        # apply forward fn to every tuple
        SCREAMING_SNAKE_CASE				:				Tuple				      = tuple(forward_fn(*a__   ) for input_tensors_chunk in zip(*a__   )   )
        # concatenate output at same dimension
        return torch.cat(a__ ,						dim=a__   )

    return forward_fn(*a__   )







def 				UpperCAmelCase_(    a__ ,						a__ ,						a__ ,						a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				Optional[int]				      = torch.ones(a__ ,						a__   )
    SCREAMING_SNAKE_CASE				:				str				      = set(a__   ) - already_pruned_heads  # Convert to set and remove already pruned heads
    for head in heads:
        # Compute how many pruned heads are before the head and move the index accordingly
        SCREAMING_SNAKE_CASE				:				Optional[Any]				      = head - sum(1 if h < head else 0 for h in already_pruned_heads   )
        SCREAMING_SNAKE_CASE				:				str				      = 0
    SCREAMING_SNAKE_CASE				:				List[str]				      = mask.view(-1   ).contiguous().eq(1   )
    SCREAMING_SNAKE_CASE				:				torch.LongTensor				      = torch.arange(len(a__   )   )[mask].long()
    return heads, index







def 				UpperCAmelCase_(    *a__ ,						a__ = None   ):



    """simple docstring"""



    return torch.meshgrid(*a__ ,						indexing=a__   )







def 				UpperCAmelCase_(    a__   ):



    """simple docstring"""



    return tensor.device, storage_ptr(a__   ), storage_size(a__   )
