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 自动生成