题目描述

在一个社交聊天软件里，有 $n$ 名用户，一开始，所有用户之间都不存在好友关系，接下来有 $m$ 条关于用户的操作记录：

• 第一种记录形式为 + x y，表示两名用户 $x$ 与 $y$ 结成了朋友关系；
• 第二种记录形式为 - x y，表示两名用户 $x$ 与 $y$ 解除了朋友关系；
• 第三种记录形式为 ! x，表示用户 $x$ 群发了一张照片，与 $x$ 为好友的用户可以收到这张照片。若某人在照片发出后才成为 $x$ 的好友，是收不到这张照片的。

经过这些操作之后，请统计并输出每一名用户收到了多少张照片。

输入格式

• 第一行：两个整数 $n$ 与 $m$；
• 接下来 $m$ 行：每行表示一条操作记录，格式如题面所述。为了化简问题，特别保证：
  • 当输入记录中出现 + x y 时，$x$ 与 $y$ 一定尚未结成好友关系
  • 当输入记录中出现 - x y 时，$x$ 与 $y$ 一定已经结成好友关系
• 也就是说，这两类记录永远不是冗余的。

输出格式

单独一行：$n$ 个整数，分别表示 $n$ 名用户收到的照片数量。

3 5
+ 1 2
! 1
- 1 2
! 1
! 3

0 1 0

数据范围

• 对于 $30\%$ 的数据，$n\leq 2000$，$m\leq 5000$。
• 对于 $60\%$ 的数据，$n\leq 200,000$，$m\leq 500,000$。
• 对于 $100\%$ 的数据，$2\leq n\leq 500,000$，$1\leq m\leq 1,000,000$。