"""
p103 — Design Twitter (LC 355)

getNewsFeed(uid) = 10 most-recent tweets from uid + uid's followees.

Two designs:
 1. Twitter        — heap-merge of K (= followees + 1) sorted streams; lazy push-on-pop.
                     O(K + 10 log K) where K = len(followees) + 1.
 2. TwitterBrute   — gather-all then sort. O(N log N) where N = total relevant tweets.

INVARIANT (heap merge): the heap always contains the *next available* (most-recent unread)
tweet from each stream that still has tweets. Pop 10; after each pop, push the next-older
tweet from that same stream if any remain.

Monotonic counter: self.time increments on every postTweet. Larger = more recent.
"""
from __future__ import annotations
import heapq
import random
from collections import defaultdict
from typing import Dict, List, Set, Tuple


FEED_SIZE = 10


class Twitter:
    def __init__(self) -> None:
        self.time = 0
        self.tweets: Dict[int, List[Tuple[int, int]]] = defaultdict(list)  # uid -> [(time, tid)]
        self.follows: Dict[int, Set[int]] = defaultdict(set)               # uid -> set of followees

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        self.tweets[userId].append((self.time, tweetId))

    def getNewsFeed(self, userId: int) -> List[int]:
        candidates = self.follows[userId] | {userId}
        # Max-heap via negation. Seed with the LAST (= most recent) tweet of each user.
        heap: List[Tuple[int, int, int]] = []  # (-time, uid, idx_into_tweets[uid])
        for uid in candidates:
            ts = self.tweets.get(uid)
            if ts:
                last = len(ts) - 1
                heap.append((-ts[last][0], uid, last))
        heapq.heapify(heap)
        out: List[int] = []
        while heap and len(out) < FEED_SIZE:
            neg_t, uid, idx = heapq.heappop(heap)
            out.append(self.tweets[uid][idx][1])
            if idx > 0:
                prev = self.tweets[uid][idx - 1]
                heapq.heappush(heap, (-prev[0], uid, idx - 1))
        return out

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId == followeeId:
            return  # self-follow is a no-op; getNewsFeed includes self anyway
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId == followeeId:
            return
        self.follows[followerId].discard(followeeId)


class TwitterBrute:
    """Gather-all + sort oracle."""

    def __init__(self) -> None:
        self.time = 0
        self.tweets: Dict[int, List[Tuple[int, int]]] = defaultdict(list)
        self.follows: Dict[int, Set[int]] = defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        self.tweets[userId].append((self.time, tweetId))

    def getNewsFeed(self, userId: int) -> List[int]:
        candidates = self.follows[userId] | {userId}
        all_relevant: List[Tuple[int, int]] = []
        for uid in candidates:
            all_relevant.extend(self.tweets.get(uid, []))
        all_relevant.sort(key=lambda x: -x[0])
        return [tid for _, tid in all_relevant[:FEED_SIZE]]

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId == followeeId:
            return
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId == followeeId:
            return
        self.follows[followerId].discard(followeeId)


def edge_cases() -> None:
    # LC example
    t = Twitter()
    t.postTweet(1, 5)
    assert t.getNewsFeed(1) == [5]
    t.follow(1, 2)
    t.postTweet(2, 6)
    assert t.getNewsFeed(1) == [6, 5]
    t.unfollow(1, 2)
    assert t.getNewsFeed(1) == [5]

    # Empty feed
    t = Twitter()
    assert t.getNewsFeed(99) == []

    # Self-follow no-op (own tweets still appear)
    t = Twitter()
    t.postTweet(1, 100)
    t.follow(1, 1)
    assert t.getNewsFeed(1) == [100]

    # Unfollow someone you don't follow — no-op
    t = Twitter()
    t.unfollow(1, 2)  # must not raise
    assert t.getNewsFeed(1) == []

    # More than 10 tweets — feed cap
    t = Twitter()
    for i in range(20):
        t.postTweet(1, i)
    assert t.getNewsFeed(1) == list(range(19, 9, -1))

    print("edge_cases OK")


def stress_test(trials: int = 80, ops: int = 200) -> None:
    rng = random.Random(42)
    for trial in range(trials):
        a = Twitter()
        b = TwitterBrute()
        for _ in range(ops):
            op = rng.choices(
                ["post", "follow", "unfollow", "feed"],
                weights=[5, 3, 2, 4],
            )[0]
            if op == "post":
                uid = rng.randint(1, 6)
                tid = rng.randint(0, 10_000)
                a.postTweet(uid, tid)
                b.postTweet(uid, tid)
            elif op == "follow":
                u, v = rng.randint(1, 6), rng.randint(1, 6)
                a.follow(u, v)
                b.follow(u, v)
            elif op == "unfollow":
                u, v = rng.randint(1, 6), rng.randint(1, 6)
                a.unfollow(u, v)
                b.unfollow(u, v)
            else:
                uid = rng.randint(1, 6)
                ra, rb = a.getNewsFeed(uid), b.getNewsFeed(uid)
                assert ra == rb, (trial, uid, ra, rb)
    print(f"stress_test OK ({trials} trials)")


if __name__ == "__main__":
    edge_cases()
    stress_test()