AT_digitalarts_3 Chokutter

高桥君是一位对网络安全颇有兴趣，并希望加入数字艺术公司的年轻人。他正在审查自己开发的“吐槽型”社交网络「Chokutter」的日志，这个平台在部分竞赛程序员中非常受欢迎。以下是「Chokutter」的操作规则。 1. 用户可以发布“微博”，并且发布的内容会显示在自己的时间线上。 2. 用户可以关注其他用户： - 关注后，所关注的用户A发布的新微博会显示在你的时间线上，但在关注之前的微博不会显示。 - 当你关注用户A时，用户A也会自动关注你。 - 因此，你和用户A会互相看到对方发布的新微博。 - 注意：不能关注已经关注的人或自己。 3. 用户可以取消对其他用户的关注： - 取消关注后，用户A的新微博将不再显示在你的时间线上，但之前已经显示的微博不受影响。 - 当你取消对用户A的关注时，用户A也会自动取消对你的关注。 - 要注意的是，取消关注后，用户A将不会再看到你新的微博。 - 注意：不能取消对未关注的人的关注，也不能取消对自己的关注。 请注意，这些规则与其他类似的服务有所不同。 高桥君计划根据Chokutter日志，制作一个用户时间线上微博数量的排行榜。给定一个整数 $ K $，请输出在排行榜中第 $ K $ 位的用户其时间线上显示的微博数量。初始状态下，所有用户均未关注其他用户。输入格式如下： ### 输入格式 - 第一行输入三个整数 $ N $、$ M $ 和 $ K $，分别表示用户数、日志行数以及目标排名位置。其中 $ 2 \leq N \leq 100,000 $，$ 0 \leq M \leq 100,000 $，$ 1 \leq K \leq N $。 - 接下来 $ M $ 行：每行包含一条日志记录 $ s_i $。 - 每条日志 $ s_i $ 有三种格式，其中整数 $ j $ 和 $ k $ 表示用户编号，$ 1 \leq j, k \leq N $ 且 $ j \neq k $。 - 如果 $ s_i $ 的首字符是 `t`，表示用户 $ j $ 发布了一条微博。 - 如果 $ s_i $ 的首字符是 `f`，表示用户 $ j $ 关注了用户 $ k $。 - 如果 $ s_i $ 的首字符是 `u`，表示用户 $ j $ 取消关注了用户 $ k $。 ### 输出格式 - 输出排名第 $ K $ 位的用户的时间线上显示的微博数量。最后输出一个换行符。 ### 数据范围与提示 - $ 2 \leq N \leq 100,000 $ - $ 0 \leq M \leq 100,000 $ - $ 1 \leq K \leq N $ ### 示例 #### 输入 ``` 5 9 1 t 1 f 1 3 f 2 1 t 2 t 1 u 3 1 t 1 t 5 t 5 ``` #### 输出 ``` 4 ``` #### 解释 - 初始状态下：所有用户都未关注他人。 - 用户1发布一条微博，只有用户1能看到。 - 用户1关注了用户3，系统也自动让用户3关注用户1。 - 用户2关注了用户1，系统也自动让用户1关注用户2。 - 用户2发布了一条微博，用户1和用户2都能看到。 - 用户1再次发布一条微博，用户1、用户2和用户3都能看到。 - 用户3取消了对用户1的关注，用户1也自动取消了对用户3的关注。 - 用户1发布一条微博，用户1和用户2能看到。 - 用户5发布两条微博，只有用户5能看到。 - 最终，每个用户时间线上显示的微博数量为：用户1有4条，用户2有3条，用户3有1条，用户4有0条，用户5有2条。 - 因此，第1名的用户是用户1，时间线上显示的微博数量为4。 #### 输入示例以及对应输出请参考上面的描述。 **本翻译由 AI 自动生成**

无

无