P3998 [SHOI2013] Posting Weibo

The newly launched SH Weibo has $n$ users (labeled $1\sim n$). During this brief month, users were very active, and there are $m$ records in chronological order: ```plain ! x 表示用户 x 发了一条微博； + x y 表示用户 x 和用户 y 成为了好友 − x y 表示用户 x 和用户 y 解除了好友关系 ``` When a user posts a Weibo, all of their friends (direct connections) will see the message. Assume that initially no one is friends with anyone else, and all records are valid (i.e., when `+ x y` occurs, $x$ and $y$ are not friends; when `− x y` occurs, $x$ and $y$ are friends). After these $m$ records, determine how many messages each user has seen.

The first line contains two integers $n$, $m$. The next $m$ lines contain the records in chronological order, each formatted as described above and separated by spaces.

Output one line with $n$ space-separated integers (no trailing space). The $i$-th number denotes the number of messages seen by user $i$.

For $100\%$ of the testdata, $n \leq 200000$, $m \leq 500000$. Translated by ChatGPT 5