LRU Cache with BFS Enhancement

Design an LRU (Least Recently Used) cache data structure that supports the following operations with a BFS (Breadth-First Search) enhancement: get(key): Return the value (always positive) of the key if it exists in the cache, otherwise return -1. put(key, value): Update the value of the key if the key exists. Otherwise, insert the key-value pair. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. Assume the cache has a capacity of n, and provide a sample sequence of operations to test your implementation: get(1) put(2, 2) put(3, 3) get(2) put(4, 4) get(1) Where the cache capacity n = 2. Example Input ['LRUCache','put','put','get','put','get','put','get','get','get'] [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]