

'''simple docstring'''

from collections import deque





def lowerCamelCase		(  __lowerCamelCase				:					Dict					)		->List[Any]:
    return input(__lowerCamelCase					).strip().split(""" """					)





def lowerCamelCase		(  __lowerCamelCase				:					Optional[int]      , __lowerCamelCase				:					Tuple					)		->dict[int, list[int]]:
    _SCREAMING_SNAKE_CASE             =    {}
    for i in range(__lowerCamelCase					):
        _SCREAMING_SNAKE_CASE             =    []

    for e in range(__lowerCamelCase					):
        _SCREAMING_SNAKE_CASE             =    (int(__lowerCamelCase					) for i in _input(F'Edge {e + 1}: <node1> <node2> '					))
        graph[x].append(__lowerCamelCase					)
    return graph





def lowerCamelCase		(  __lowerCamelCase				:					Optional[Any]      , __lowerCamelCase				:					List[Any]					)		->dict[int, list[int]]:
    _SCREAMING_SNAKE_CASE             =    {}
    for i in range(__lowerCamelCase					):
        _SCREAMING_SNAKE_CASE             =    []

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





def lowerCamelCase		(  __lowerCamelCase				:					str      , __lowerCamelCase				:					str					)		->dict[int, list[tuple[int, int]]]:
    _SCREAMING_SNAKE_CASE             =    {}
    for i in range(__lowerCamelCase					):
        _SCREAMING_SNAKE_CASE             =    []

    for e in range(__lowerCamelCase					):
        _SCREAMING_SNAKE_CASE             =    (int(__lowerCamelCase					) 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__":
      lowercase_			       =				(int(i) for i in _input("""Number of nodes and edges: """))

      lowercase_			       =				int(
          _input(
              """Press 1 or 2 or 3 \n"""
              """1. Unweighted directed \n"""
              """2. Unweighted undirected \n"""
              """3. Weighted undirected \n"""
          )[0]
      )

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





def lowerCamelCase		(  __lowerCamelCase				:					Optional[Any]      , __lowerCamelCase				:					List[str]					)		->Any:
    _SCREAMING_SNAKE_CASE             =    {s}, [s]
    print(__lowerCamelCase					)
    while _s:
        _SCREAMING_SNAKE_CASE             =    0
        for i in g[_s[-1]]:
            if i not in vis:
                _s.append(__lowerCamelCase					)
                vis.add(__lowerCamelCase					)
                _SCREAMING_SNAKE_CASE             =    1
                print(__lowerCamelCase					)
                break
        if not flag:
            _s.pop()





def lowerCamelCase		(  __lowerCamelCase				:					Tuple      , __lowerCamelCase				:					str					)		->int:
    _SCREAMING_SNAKE_CASE             =    {s}, deque([s]					)
    print(__lowerCamelCase					)
    while q:
        _SCREAMING_SNAKE_CASE             =    q.popleft()
        for v in g[u]:
            if v not in vis:
                vis.add(__lowerCamelCase					)
                q.append(__lowerCamelCase					)
                print(__lowerCamelCase					)





def lowerCamelCase		(  __lowerCamelCase				:					Dict      , __lowerCamelCase				:					List[Any]					)		->Tuple:
    _SCREAMING_SNAKE_CASE             =    {s: 0}, set(), {s: 0}
    while True:
        if len(__lowerCamelCase					) == len(__lowerCamelCase					) - 1:
            break
        _SCREAMING_SNAKE_CASE             =    10_0000
        for i in dist:
            if i not in known and dist[i] < mini:
                _SCREAMING_SNAKE_CASE             =    dist[i]
                _SCREAMING_SNAKE_CASE             =    i
        known.add(__lowerCamelCase					)
        for v in g[u]:
            if v[0] not in known and dist[u] + v[1] < dist.get(v[0]      , 10_0000					):
                _SCREAMING_SNAKE_CASE             =    dist[u] + v[1]
                _SCREAMING_SNAKE_CASE             =    u
    for i in dist:
        if i != s:
            print(dist[i]					)





def lowerCamelCase		(  __lowerCamelCase				:					Union[str, Any]      , __lowerCamelCase				:					Optional[Any]=None      , __lowerCamelCase				:					Any=None					)		->Union[str, Any]:
    if q is None:
        _SCREAMING_SNAKE_CASE             =    [1]
    if ind is None:
        _SCREAMING_SNAKE_CASE             =    [0] * (len(__lowerCamelCase					) + 1)  # SInce oth Index is ignored
        for u in g:
            for v in g[u]:
                ind[v] += 1
        _SCREAMING_SNAKE_CASE             =    deque()
        for i in g:
            if ind[i] == 0:
                q.append(__lowerCamelCase					)
    if len(__lowerCamelCase					) == 0:
        return
    _SCREAMING_SNAKE_CASE             =    q.popleft()
    print(__lowerCamelCase					)
    for w in g[v]:
        ind[w] -= 1
        if ind[w] == 0:
            q.append(__lowerCamelCase					)
    topo(__lowerCamelCase      , __lowerCamelCase      , __lowerCamelCase					)





def lowerCamelCase		(  )		->str:
    _SCREAMING_SNAKE_CASE             =    input().strip()
    _SCREAMING_SNAKE_CASE             =    []
    for _ in range(__lowerCamelCase					):
        a.append(map(__lowerCamelCase      , input().strip().split()					)					)
    return a, n





def lowerCamelCase		(  __lowerCamelCase				:					Optional[Any]					)		->Tuple:
    (_SCREAMING_SNAKE_CASE)             =    a_and_n
    _SCREAMING_SNAKE_CASE             =    list(__lowerCamelCase					)
    _SCREAMING_SNAKE_CASE             =    [[0] * n for i in range(__lowerCamelCase					)]
    for k in range(__lowerCamelCase					):
        for i in range(__lowerCamelCase					):
            for j in range(__lowerCamelCase					):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    _SCREAMING_SNAKE_CASE             =    dist[i][k] + dist[k][j]
                    _SCREAMING_SNAKE_CASE             =    k
    print(__lowerCamelCase					)





def lowerCamelCase		(  __lowerCamelCase				:					Tuple      , __lowerCamelCase				:					List[str]					)		->Optional[int]:
    _SCREAMING_SNAKE_CASE             =    {s: 0}, set(), {s: 0}
    while True:
        if len(__lowerCamelCase					) == len(__lowerCamelCase					) - 1:
            break
        _SCREAMING_SNAKE_CASE             =    10_0000
        for i in dist:
            if i not in known and dist[i] < mini:
                _SCREAMING_SNAKE_CASE             =    dist[i]
                _SCREAMING_SNAKE_CASE             =    i
        known.add(__lowerCamelCase					)
        for v in g[u]:
            if v[0] not in known and v[1] < dist.get(v[0]      , 10_0000					):
                _SCREAMING_SNAKE_CASE             =    v[1]
                _SCREAMING_SNAKE_CASE             =    u
    return dist





def lowerCamelCase		(  )		->List[str]:
    _SCREAMING_SNAKE_CASE             =    map(__lowerCamelCase      , input().split(""" """					)					)
    _SCREAMING_SNAKE_CASE             =    []
    for _ in range(__lowerCamelCase					):
        edges.append(map(__lowerCamelCase      , input().split(""" """					)					)					)
    return edges, n





def lowerCamelCase		(  __lowerCamelCase				:					List[str]					)		->Optional[int]:
    (_SCREAMING_SNAKE_CASE)             =    e_and_n
    e.sort(reverse=__lowerCamelCase      , key=lambda __lowerCamelCase					: x[2]					)
    _SCREAMING_SNAKE_CASE             =    [{i} for i in range(1      , n + 1					)]
    while True:
        if len(__lowerCamelCase					) == 1:
            break
        print(__lowerCamelCase					)
        _SCREAMING_SNAKE_CASE             =    e.pop()
        for i in range(len(__lowerCamelCase					)					):
            if x[0] in s[i]:
                break
        for j in range(len(__lowerCamelCase					)					):
            if x[1] in s[j]:
                if i == j:
                    break
                s[j].update(s[i]					)
                s.pop(__lowerCamelCase					)
                break






def lowerCamelCase		(  __lowerCamelCase				:					List[str]					)		->Union[str, Any]:
    _SCREAMING_SNAKE_CASE             =    []
    for node in graph:
        if not graph[node]:
            isolated.append(__lowerCamelCase					)
    return isolated










'''simple docstring'''

import math
from timeit import timeit





def lowerCamelCase		(  __lowerCamelCase				:					int					)		->int:
    _SCREAMING_SNAKE_CASE             =    0
    _SCREAMING_SNAKE_CASE             =    abs(__lowerCamelCase					)
    while True:
        _SCREAMING_SNAKE_CASE             =    n // 10
        digits += 1
        if n == 0:
            break
    return digits





def lowerCamelCase		(  __lowerCamelCase				:					int					)		->int:
    return 1 if n == 0 else math.floor(math.log(abs(__lowerCamelCase					)      , 10					) + 1					)





def lowerCamelCase		(  __lowerCamelCase				:					int					)		->int:
    return len(str(abs(__lowerCamelCase					)					)					)





def lowerCamelCase		(  )		->None:
    from collections.abc import Callable

    def benchmark_a_function(__lowerCamelCase				:					Callable      , __lowerCamelCase				:					int					) -> None:
        _SCREAMING_SNAKE_CASE             =    F'{func.__name__}({value})'
        _SCREAMING_SNAKE_CASE             =    timeit(F'__main__.{call}'      , setup="""import __main__"""					)
        print(F'{call}: {func(__lowerCamelCase					)} -- {timing} seconds'					)

    for value in (26_2144, 1125_8999_0684_2624, 126_7650_6002_2822_9401_4967_0320_5376):
        for func in (num_digits, num_digits_fast, num_digits_faster):
            benchmark_a_function(__lowerCamelCase      , __lowerCamelCase					)
        print()


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      benchmark()



