class ABNum:
    def __init__(self, value: str | int, pad=-1) -> None:
        self.pad = pad
        if isinstance(value, int):
            self.value = value
            return
        value_list = [self.map_to_int(v) for v in reversed(value)]
        self.pad = len(value_list)
        self.value = 0
        for index, v in enumerate(value_list):
            self.value += v * 36 ** index

    def plusOne(self):
        self.value += 1

    def __add__(self, other):
        if isinstance(other, int):
            value = self.value + other
            return ABNum(value, self.pad)

    def __str__(self):
        value = self.value
        value_list = []
        while True:
            value, div = divmod(value, 36)
            value_list.append(div)
            if value < 36:
                value_list.append(value)
                break
        pad_num = self.pad - len(value_list)
        value_list.reverse()
        if pad_num > 0:
            value_list = [0] * pad_num + value_list
        return ''.join([self.map_to_str(v) for v in value_list])

    @staticmethod
    def map_to_int(v: str) -> int:
        assert len(v) == 1
        if v.isdecimal():
            return int(v)
        return ord(v) - 87

    @staticmethod
    def map_to_str(v: int) -> str:
        if v >= 0 and v <= 9:
            return str(v)
        return chr(87+v)

col = df["col_name"]

cols = df[["col_name_1", "col_name_2", "col_name_3"]]

sub_df = df.loc[]

sub_df = df.iloc[2:8, 1:9]

df.loc[lambda s: s['shield'] == 8, :]

df['col_name'].apply(func)

func(df['col_name'])

df.apply(func, axis=1)

df['col_name'].map(func)

[func(i) for i in df['col_name']]

df['col_name'].reduce(func)

func(func(func(func(s1, s2), s3), s4)...)

df = pd.concat(df_1, df_2)

df = pd.merge(df_1, df_2, left_on="left_col", right_on="right_col", how="left")

df.groupby('col_name')

from contextvars import ContextVar

_state = threading.local()

def _get_context():
    ctx = getattr(_state, 'context', None)
    if ctx is None:
        ctx = Context()
        _state.context = ctx
    return ctx


def _set_context(ctx):
    _state.context = ctx

class ContextMeta(type(collections.abc.Mapping)):

    # contextvars.Context is not subclassable.

    def __new__(mcls, names, bases, dct):
        cls = super().__new__(mcls, names, bases, dct)
        if cls.__module__ != 'contextvars' or cls.__name__ != 'Context':
            raise TypeError("type 'Context' is not an acceptable base type")
        return cls


class Context(collections.abc.Mapping, metaclass=ContextMeta):

    def __init__(self):
        self._data = immutables.Map()
        self._prev_context = None

    def run(self, callable, *args, **kwargs):
        if self._prev_context is not None:
            raise RuntimeError(
                'cannot enter context: {} is already entered'.format(self))

        self._prev_context = _get_context()
        try:
            _set_context(self)
            return callable(*args, **kwargs)
        finally:
            _set_context(self._prev_context)
            self._prev_context = None

    def copy(self):
        new = Context()
        new._data = self._data
        return new

    def __getitem__(self, var):
        if not isinstance(var, ContextVar):
            raise TypeError(
                "a ContextVar key was expected, got {!r}".format(var))
        return self._data[var]

    def __contains__(self, var):
        if not isinstance(var, ContextVar):
            raise TypeError(
                "a ContextVar key was expected, got {!r}".format(var))
        return var in self._data

    def __len__(self):
        return len(self._data)

    def __iter__(self):
        return iter(self._data)

class ContextVarMeta(type):

    # contextvars.ContextVar is not subclassable.

    def __new__(mcls, names, bases, dct):
        cls = super().__new__(mcls, names, bases, dct)
        if cls.__module__ != 'contextvars' or cls.__name__ != 'ContextVar':
            raise TypeError("type 'ContextVar' is not an acceptable base type")
        return cls

    def __getitem__(cls, name):
        return


class ContextVar(metaclass=ContextVarMeta):

    def __init__(self, name, *, default=_NO_DEFAULT):
        if not isinstance(name, str):
            raise TypeError("context variable name must be a str")
        self._name = name
        self._default = default

    @property
    def name(self):
        return self._name

    def get(self, default=_NO_DEFAULT):
        ctx = _get_context()
        try:
            return ctx[self]
        except KeyError:
            pass

        if default is not _NO_DEFAULT:
            return default

        if self._default is not _NO_DEFAULT:
            return self._default

        raise LookupError

    def set(self, value):
        ctx = _get_context()
        data = ctx._data
        try:
            old_value = data[self]
        except KeyError:
            old_value = Token.MISSING

        updated_data = data.set(self, value)
        ctx._data = updated_data
        return Token(ctx, self, old_value)

    def reset(self, token):
        if token._used:
            raise RuntimeError("Token has already been used once")

        if token._var is not self:
            raise ValueError(
                "Token was created by a different ContextVar")

        if token._context is not _get_context():
            raise ValueError(
                "Token was created in a different Context")

        ctx = token._context
        if token._old_value is Token.MISSING:
            ctx._data = ctx._data.delete(token._var)
        else:
            ctx._data = ctx._data.set(token._var, token._old_value)

        token._used = True

    def __repr__(self):
        r = '<ContextVar name={!r}'.format(self.name)
        if self._default is not _NO_DEFAULT:
            r += ' default={!r}'.format(self._default)
        return r + ' at {:0x}>'.format(id(self))

_cv_app: ContextVar["AppContext"] = ContextVar("flask.app_ctx")
app_ctx: "AppContext" = LocalProxy(
    _cv_app, unbound_message=_no_app_msg
)
current_app: "Flask" = LocalProxy(
    _cv_app, "app", unbound_message=_no_app_msg
)
g: "_AppCtxGlobals" = LocalProxy(
    _cv_app, "g", unbound_message=_no_app_msg
)

_cv_request: ContextVar["RequestContext"] = ContextVar("flask.request_ctx")
request_ctx: "RequestContext" = LocalProxy(
    _cv_request, unbound_message=_no_req_msg
)
request: "Request" = LocalProxy(
    _cv_request, "request", unbound_message=_no_req_msg
)
session: "SessionMixin" = LocalProxy(
    _cv_request, "session", unbound_message=_no_req_msg
)

class AppContext:
    """The app context contains application-specific information. An app
    context is created and pushed at the beginning of each request if
    one is not already active. An app context is also pushed when
    running CLI commands.
    """

    def __init__(self, app: "Flask") -> None:
        self.app = app
        self.url_adapter = app.create_url_adapter(None)
        self.g: _AppCtxGlobals = app.app_ctx_globals_class()
        self._cv_tokens: t.List[contextvars.Token] = []

    def push(self) -> None:
        """Binds the app context to the current context."""
        self._cv_tokens.append(_cv_app.set(self))
        appcontext_pushed.send(self.app)

    def pop(self, exc: t.Optional[BaseException] = _sentinel) -> None:  # type: ignore
        """Pops the app context."""
        try:
            if len(self._cv_tokens) == 1:
                if exc is _sentinel:
                    exc = sys.exc_info()[1]
                self.app.do_teardown_appcontext(exc)
        finally:
            ctx = _cv_app.get()
            _cv_app.reset(self._cv_tokens.pop())

        if ctx is not self:
            raise AssertionError(
                f"Popped wrong app context. ({ctx!r} instead of {self!r})"
            )

        appcontext_popped.send(self.app)

    def __enter__(self) -> "AppContext":
        self.push()
        return self

    def __exit__(
        self,
        exc_type: t.Optional[type],
        exc_value: t.Optional[BaseException],
        tb: t.Optional[TracebackType],
    ) -> None:
        self.pop(exc_value)

url_map = Map([
    Rule('/', endpoint='new_url'),
    Rule('/<short_id>', endpoint='follow_short_link'),
    Rule('/<short_id>+', endpoint='short_link_details')
])

adapter = url_map.bind_to_environ(request.environ)

for endpoint, values in adapter.match():
    do_something()

@app.route('/query/users/')
def show_users():
    users = User.query.all()
    return render_template('users.html', users=users)

@app.route('/query/goods/')
def show_goods():
    users = Goods.query.all()
    return render_template('goods.html', goods=goods)

from flask.views import View

class ListView(View):

    def get_template_name(self):
        raise NotImplementedError()

    def render_template(self, context):
        return render_template(self.get_template_name(), **context)

    def dispatch_request(self):
        context = {'objects': self.get_objects()}
        return self.render_template(context)

class UserView(ListView):

    def get_template_name(self):
        return 'user.html'

    def get_objects(self):
        return User.query.all()

def _render(app: "Flask", template: Template, context: t.Dict[str, t.Any]) -> str:
    app.update_template_context(context)
    before_render_template.send(app, template=template, context=context)
    rv = template.render(context)
    template_rendered.send(app, template=template, context=context)
    return rv

def _stream(
    app: "Flask", template: Template, context: t.Dict[str, t.Any]
) -> t.Iterator[str]:
    app.update_template_context(context)
    before_render_template.send(app, template=template, context=context)

    def generate() -> t.Iterator[str]:
        yield from template.generate(context)
        template_rendered.send(app, template=template, context=context)

    rv = generate()

    # If a request context is active, keep it while generating.
    if request:
        rv = stream_with_context(rv)

    return rv

# context 1 or context 2
if context_1:
    do_some_thing()
# target context

# context 1 of context 2 or ...
if context_1:
    do_some_thing_1()
elif context_2:
    do_some_thing_2()
elif context_3:
    do_some_thing_3()
# target context

# context 1 of context 2 or ...
if context_1:
    do_some_thing_1()
elif context_2:
    do_some_thing_2()
elif context_3:
    do_some_thing_3()
# end

for _ in range(len(array)):    # [0, length) -> [0, length-1]
    do_some_thing()

while not target_context:
    do_some_thing()
# target context

def feb_rec(n):
    # 基础值
    if n in [0, 1]:
        return n

    # 递归锚点
    result_rec_2 = feb_rec(n-2)
    result_rec_1 = feb_rec(n-1)

    # 计算组合值
    result_rec = result_rec_1 + result_rec_2

    # 返回组合值
    return result_rec

def LCA(node, p, q):
    result = None
    def LCA_rec(node):
        # 定义基础值 [None, p, q]
        if not node or node is p or node is q:
            return node

        # 递归锚点
        left = LCA_rec(node.left)
        right = LCA_rec(node.right)

        # 计算组合值
        # [None & None] => None
        # [None & [p | q]] => [p | q]
        # [p & q] => LCA
        if left is None and right is None:
            return None
        elif (left is p and right is q) or (left is q and right is p):
            result = node
            return node
        elif left is None:
            return right
        else:
            return left

    LCA_rec(root, p, q)
    return result

def mirror(root):
    def mirror_rec(left, right):
        # 基础值
        if not left and not right:
            return True
        elif not left or not right:
            return False
        if left.val != right.val:
            return False

        # 递归锚点
        mirror_out = mirror_rec(left.left, right.right)
        mirror_in = mirror_rec(left.right, right.left)

        # 计算组合值
        mirror = mirror_out and mirror_in

        return mirror

def rec(node: ListNode):
    # 终止条件写在前面
    next_node = node.next
    if not next_node:
        return

    # 递归点
    rec(next_node)

    # 后序
    next_node.next = node

    # 调整
    if node is header:
        next_node = None

def left_binsearch(nums, left, right, value):
    """非降序列第一个不小于value的位置."""
    while left < right:
        mid = left + (right-left)//2
        if nums[mid] < value:
            left = mid + 1
        else:
            right = mid
    return left

def right_binsearch(nums, left, right, value):
    """非降序列第一个大于value的位置."""
    while left < right:
        mid = left + (right-left)//2
        if nums[mid] <= value:
            left = mid + 1
        else:
            right = mid
    return left

grid = [[0] * width for _ in range(height)]

for r in range(len(grid)):
    for c in range(len(grid[0])):
        grid[r][c] = 0

for r in range(len(grid)):
    c = r
    grid[r][c] = 0

for r in range(len(grid)):
    c = len(grid)-1-r
    grid[r][c] = 0

d = {(+1, +1), (+1, -1), (-1, +1), (-1, -1)}
pos = (0, 0)

i <= 1
i >= 1  # 向下去整

n & 1 == True # 奇数 否则为偶数

n <<= 1

n >>= 1

stack = []
for i in range(n):
    while (len(stack) != 0 and stakc[-1] > nums[i]):
        stack.pop()
    stack.append(nums[i])

# 初始化
uf = {item: -1 for item in [1, 2, 3, 4, 5, 6, 7]} 负数表示此为根，且绝对值表示此类的大小

# 查 根
def find(uf: dict, one: int) -> int:
    while uf[one] > 0:
        one = uf[one]
    return one

# 并 切记需要并根元素
def union(uf: dict, one, other) -> None:
    # 查根
    root_one = find(uf, one)
    root_other = find(uf, other)

    # 判断/ 也是一种逻辑切分
    if root_one == root_other:
        return

    # 将小树并到大树上，尽量保持平衡
    if uf[root_one] < uf[root_other]:
        root_one, root_other = root_other, root_one

    uf[root_other] += uf[root_one]
    uf[root_one] = root_other

# 初始化
heap = [0] * 50

# 获取节点数量
def get_num(heap):
    return heap[0]

# 下沉 pos 位置的元素
def sink(heap, pos):
    # 获取当前节点值, 左右节点值
    current, left, right = heap[pos], heap[2*pos], heap[2*pos+1]

    # 当前值最小, 停止下沉
    if current <= left and current <= right:
        return

    # 当前值最大, 挑选左右较小节点
    if current > left and current > right:
        small_pos = 2*pos if heap[2*pos] < heap[2*pos+1] else 2*pos+1
    # 否则若左节点较小
    elif current > left:
        small_pos = 2*pos
    # 否则必定右节点较小
    else:
        small_pos = 2*pos+1

    heap[pos], heap[small_pos] = heap[small_pos], heap[pos]

    # 递归点
    sink(heap, small_pos)

# 上浮操作
def up(heap, pos):
    # 获取父节点
    parent_pos = pos // 2

    # 若父节点是元节点, 或父节点比当前节点小
    if parent_pos == 0 or heap[parent_pos] <= heap[pos]:
        return

    # 交换父子节点
    heap[parent_pos], heap[pos] = heap[pos], heap[parent_pos]

    # 递归点
    up(heap, parent_pos)

# 取元素
def pop(heap):
    # 先判断是否有元素
    if heap[0] <= 0:
        return None

    # 取出堆顶元素
    value = heap[1]

    # 将最后元素置于堆顶
    heap[1], heap[heap[0]] = heap[heap[0]], 0
    # 元素计数 -1
    heap[0] -= 1
    # 堆顶元素下沉
    sink(heap, 1)
    return value

# 放入元素
def push(heap, value):
    # 元素计数 +1
    heap[0] += 1
    # 将元素放在最后
    heap[heap[0]] = value
    # 最后元素上浮
    up(heap, heap[0])

from collections import defaultdict
adj_table = defaultdict(list)

# 添加 a -> b, 权重为 w 的边
adj_table[a].append((b, w))

def sort(nums):
    length = len(nums)

    # 外循环控制冒泡次数
    for out in range(length-1):

    # 内循环控制冒泡操作
        for inner in range(length-1-out):
            if nums[inner] > nums[inner+1]:
                nums[inner], nums[inner+1] = nums[inner+1], nums[inner]
    return nums

def sort(nums):
    length = len(nums)

    # 外循环控制未排序的范围
    for left in range(length):

        small_pos = left
        # 内循环负责寻找最小值
        for lst in range(left, length):
            if nums[lst] < nums[small_pos]:
                small_pos = lst

        # 循环结束后将选择的最小索引与外循环控制的排序部分交换
        nums[left], nums[small_pos] = nums[small_pos], nums[left]
    return nums

def sort(nums):
    length = len(nums)

    # 外循环逐个检查未排序元素
    for current_index in range(length):
        # 内循环负责将当前元素放到合适的位置
        for sorted_index in range(current_index, 0, -1):
            if nums[sorted_index-1] > nums[sorted_index]:
                nums[sorted_index], nums[sorted_index-1] = nums[sorted_index-1], nums[sorted_index]
            else:
                break

    return nums

def sort(nums):
    length = len(nums)
    h = 1

    while h < length/3: h = 3*h + 1

    while h >= 1:
        for i in range(h, length):
            for j in range(i, h-1, -h):
                if nums[j] < nums[j-h]:
                    nums[j], nums[j-h] = nums[j-h], nums[j]
                else:
                    break
        h = h // 3

    return nums

aux = [0] * len(nums)

def merge(nums, lo, mid, hi):
    left, right = lo, mid+1

    for k in range(lo, hi+1):
        aux[k] = nums[k]

    for k in range(lo, hi+1):
        if left > mid:
            nums[k] = aux[right]
            right += 1
        elif right > hi:
            nums[k] = aux[left]
            left += 1
        elif aux[left] > aux[right]:
            nums[k] = aux[right]
            right += 1
        else:
            nums[k] = aux[left]
            left += 1

def sort_u2d(nums):
    def sort_rec(nums, lo, hi):
        if lo >= hi:
            return
        mid = lo + (hi-lo)//2
        sort_rec(nums, lo, mid)
        sort_rec(nums, mid+1, hi)
        merge(nums, lo, mid, hi)

    length = len(nums)
    sort_rec(nums, 0, length-1)
    return nums

def sort_d2u(nums):
    length = len(nums)
    size = 1

    while size < length:
        for lo in range(0, length-size, 2*size):
            merge(nums, lo, lo+size-1, min(lo+size-1, length-1))
        size *= 2

    return nums

def partition(nums, lo, hi):
    left, right = lo, hi
    v = nums[lo]

    while left != right:
        while nums[right] >= v and left < right:
            right -= 1

        while nums[left] <= v and left < right:
            left += 1

        if left < right:
            nums[left], nums[right] = nums[right], nums[left]

    nums[lo], nums[left] = nums[left], nums[lo]
    return left

def _sort(nums, lo, hi):
    if lo >= hi:
        return
    k = partition(nums, lo, hi)
    _sort(nums, lo, k-1)
    _sort(nums, k+1, hi)

def sort(nums):
    random.shuffle(nums)
    _sort(nums, 0, len(nums)-1)
    return nums

def quick_sort(nums, l , r):
    if l >= r: return
    i, j = l, r
    while i < j:
        while nums[j] >= nums[l] and i < j: j -= 1
        while nums[i] <= nums[l] and i < j: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i], nums[l] = nums[l], nums[i]
    quick_sort(nums, l, i - 1)
    quick_sort(nums, i + 1, r)

def bisect_left(sequence, target, left, right):
    while left < right:
        mid = (left + right) // 2
        if sequenct[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def bisect_right(sequence, target, left, right):
    while left < right:
        mid = (left + right) // 2
        if sequenct[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

from collections import deque
def bfs(init_state):
    queue = deque([init_state])
    step = 0
    visited = set()

    def get_next_state(current_state):
        """"""
        pass

    while queue:
        for _ in range(len(queue)):
            current_state = queue.popleft()
            if current_state is ok:
                return step
            for next_state in get_next_state(current_state):
                if next_state not in visited:
                    visited.add(next_state)
                    queue.append(next_state)
    return -1

from collections import deque
def double_bfs(init_state, target_state):
    queue_init = deque([init_state])
    queue_target = deque([target_state])
    step = 0
    visited_forward = set()
    visited_backward = set()

    def get_next_state(current_state, direction):
        pass

    while not queue_init and not queue_target:
        queue, direction = queue_init, "f" if len(queue_init) < len(queue_target) else queue_target, "b"
        for _ in range(len(queue)):
            current_state = queue.popleft()
            if (direction == "f" and current_state in visited_backward) or (direction == "b" and current_state in visited_forward):
                return step

            for next_state in get_next_state(current_state, direction):
                if direction == "f" and next_state not in visited_forward:
                    visited_forward.add(next_state)
                elif direction == "b" and next_state not in visited_backward:
                    visited_backward.add(next_state)
                queue.append(next_state)
    return -1

for i in range(1, n+1):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], v[i]+dp[i][j-w[i]])

return dp[n][W]

# 字符串首
s[0]

# 越界
s[len(s)]

# 字符串尾
s[len(s)-1]

s[-1]

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        for j in range(i, -1, -1):
            if s[0:j] == s[(i+1)-j:(i+1)]:
                p[i] = j
                break
    return pi

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        for j in range(p[i-1]+1, -1, -1):
            if s[0:j] == s[(i+1)-j:(i+1)]:
                p[i] = j
                break
    return pi

def prefix_function(s):
    n = len(s)
    pi = [0] * n

    for i in range(1, n):
        j = pi[i-1]

        while not (j <= 0 or s[i] == s[j]):
            j = pi[j-1]

        if s[i] == s[j]:
            j += 1

        pi[i] = j

    return pi

from itertools import zip_longest, islice

def to_int_keys(l):
    """
    l: iterable of keys
    returns: a list with integer keys
    """
    index = {v: i for i, v in enumerate(sorted(set(l)))}
    return [index[v] for v in l]

def suffix(to_int_keys, s):
    n = len(s)
    k = 1
    ans = to_int_keys(s)
    while k < n:
        ans = to_int_keys(
            list(zip_longest(ans, islice(ans, k, None),
                             fillvalue=-1)))
        k <<= 1
    return ans

suffix(to_int_keys, 'banana')

def repeated(s):
    return s in (s+s)[1:-1]

def check(s):
    return s[:] == s[::-1]

if i == 0 or j == 0:
    LCS[i][j] = 0
elif x[i] == y[j]:
    LCS[i][j] = LCS[i-1][j-1] + 1
else: # x[i] != y[j]
    LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

if i == 0 or j == 0:
    LCS[i][j] = 0
elif x[i] == y[j]:
    LCS[i][j] = LCS[i-1][j-1] + 1
else: # x[i] != y[j]
    LCS[i][j] = 0

def N(S, s):
    return len(S.split(s))-1

def LCA(node, left, right):
    def LCA_rec(node):
        if not node or node == left or node == right:
            return node

        node_left = LCA(left, left, right)
        node_right = LCA(right, left, right)

        if node_left is None:
            return node_right
        if node_right is None:
            return node_left

    return node

# 点数 与 边数
num_vtex = 5
num_edge = 8

# 需要+1, 这是0索引导致的
# start, end, weight, 中保存了所有边的信息
start = [-1] * num_edge  # 起点
end = [-1] * num_edge  # 终点
weight = [-1] * num_edge  # 权重

# first 中存储每个顶点的第一条边
first = [-1] * num_vtex

# next 中存储某边的下一个边
next = [-1] * num_edge

# 读入边
for edge in range(num_edge):
    # 边i的下一个边为上一个对应的起始边
    next[edge] = first[start[edge]]
    # 更新起始边
    first[start[edge]] = edge

# 遍历顶点i的所有边
# 1. 找到顶点i的第一条边
k = first[i]
# 2. 遍历
while k != -1:
    print(start[k], end[k], weight[k])
    k = next[k]

# 遍历所有边
for i in range(num_vtex):
    k = first[i]
    while k != -1"
        print(start[k], end[k], weight[k])
        k = next[k]

adj_table = {}

for end, weight in adj_table[start]:
    do_some_thing(end, weight)

from collections import defaultdict
adj_table = defaultdict(list)

for start, end, weight in edges:
    adj_table[start].append((end, weight))

for end, weight in adj_table[s]:
    do_some_thing()

num_vtex = 20

adj_mat = [[INF] * num_vtex for _ in ragne(num_vtex)]

# 读入边
for start, end, weight in edges:
    adj_mat[start][end] = weight

for k in range(num_vtex):
    for start in range(num_vtex):
        for end in range(num_vtex):
            if adj_mat[start][end] > adj_mat[start][k]+adj_mat[k][end]:
                adj_mat = adj_mat[start][k] + adj_mat[k][end]

from math import inf

# 1. 初始化。假设源点为0

distance = [inf] * num_vtex
prefix = [None] * num_vtex
finished = set()
unfinish = set(vtex)

distance[0] = 0
finished.add(0)
unfinish.remove(0)

# 2. 迭代。

while unfinish:

    # unfinish 中查找最小distance的点
    min = inf
    for vtex in unfinish:
        if distance[vtex] < min:
            min = distance[vtex]
            start = vtex

    finished.add(start)
    unfinish.remove(start)

    # 松弛该点的所有出边
    for end, weight in adj_table[start]:
        if distance[start] + weight < distance[end]:
            distance[end] = dis[start] + weight
            prefix[end] = start

for _ in range(num_vtex-1):
    for edge in range(num_edge):
        if dis[end[edge]] > dis[end[edge]] + weight[edge]:
            dis[end[edge]] = dis[end[edge]] + weight[edge]

visited = [False] //
total = 0

def dfs(graph, node):
    if visited(node):
        return

    visited[node] = True
    total += 1

    for adj_node in graph.adj(node):
        dfs(graph, adj_node)

total = 0
visited = [False] //

def bfs(graph, node):
    queue = [node]

    while queue:
        for _ in range(len(queue)):
            current_node = queue.popleft()

            visited[current_node] = True

            do_some_thing()

            for adj_node in graph.adj(node):
                if not visited[adj_node]:
                    queue.append(adj_node)

class Node:
    def __init__(self, value: str, parent=None):
        self.children = {}
        self.value = value
        self.faild = None
        self.words = []
        if not parent:
            self.parent = self

def build(root):
    queue = [root]
    while queue:
        for _ in range(len(queue)):
            current_node = queue.pop(0)
            prob_node = current_node.parent.failed
            while prob_node.value != '':
                if current_node.value in prob_node.children:
                    current_node.failed = prob_node.children[current_node.value]
                    break
                prob_node = prob_node.failed
            for child_key in sorted(current_node.children.keys()):
                queue.append(current_node.children[child_key])