Implement an LRU (Least Recently Used) Cache class:

class LRUCache:
    def __init__(self, capacity: int): ...
    def get(self, key: int) -> int: ...   # -1 if not found
    def put(self, key: int, value: int): ...  # evict LRU if full

Example

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)    → 1
cache.put(3, 3) # evicts key 2
cache.get(2)    → -1

Hint: Use collections.OrderedDict or a doubly-linked list.