def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

def bfs(graph, start):
    visited = set()
    from collections import deque
    queue = deque[(start)]
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

import heapq
heap = []
heapq.heappush(heap, 3)
smallest = heapq.heappop(heap)

memo = {}
def fibonacci(n):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)

    return memo[n]

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, capacity + 1):
            if weights[i-1] <= j:
                dp[i][j] = max(values[i-1] + dp[i-1][j-weights[i-1]], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][capacity]


def backtrack(nums, path, result):
    if len(path) == len(nums):
        result.append(path[:])
        return
    
    for num in nums:
        if num not in path:
            path.append(num)
            backtrack(nums, path, result)
            path.pop()



def top_k_elemnts(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap


from collections import defaultdict
def group_anagrams(strs):
    grouped_anagrams = defauldict(list)
    for word in strs:
        sorted_word = ''.join(sorted(word))
        grouped_anagrams[sorted_word].append(word)
    return list(grouped_anagrams.values())


from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key in self.cache:
            value = self.cache[key]
            del self.cache[key]
            self.cache[key] = value
            return value
        else:
            return -1

    def put(self, key, value):
        if key in self.cahce:
            del self.cache[key]
        elif len(self.cache) == self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value


#random api things
arr.sort(key=lambda x: len(x))
for n1,n2 in zip(nums1, nums2):
    print(n1,n2)
''.join(strings)

mySet.add(1)
for k, v in map.items():
    print(k, v)

#for max heap use min heap by default and multiply -1 when push and pop
arr = [2,1,8,4,5]
heapq.heapify(arr)
while arr:
    print(heapq.heappop(arr))




def lengthofLIS(self, nums:List[int]) -> int:
    LIS = [1] * len(nums)
    for i in range(len(nums)-1, -1, -1):
        for j in range(i+1, len(nums)):
            if nums[i] < nums[j]:
                LIS[i] = max(LIS[i], 1+LIS[j])
    return max(LIS)