問題文
他目前正在检查他运行的“推文型”SNS 的日志。
这个SNS被称为“Chokutter”,在一些有竞争力的程序员中很受欢迎。
“Chokutter”的规格说明如下。
- 您可以“发推文”短句。
- 您的推文将显示在您的时间轴上。
- 您可以“关注”您以外的用户。
- 当您关注某个用户A时,此后该用户A发布的所有推文都会显示在您的时间线上。您关注之前的推文将不会显示。
- 在Chokutter上,如果您关注用户A,系统将强制用户A同时关注您。
- 请注意,您关注的推文将同时显示在您和用户 A 的时间线上。
- 您无法关注您已经关注的人或您自己。
- 您可以“取消关注”除您自己之外的用户。
- 如果您取消关注某个用户A,则关注状态将被取消,取消关注后用户A的推文将不再显示在您的时间轴上。最初可见的推文将按原样显示。
- 在Chokutter中,如果您取消关注用户A,系统将强制用户A同时取消关注您。
- 由上可知,您取消关注的用户A的时间轴上将不再显示您的推文。
- 您无法取消关注您不关注的人或您自己。
Takahashi 希望根据 Chokutter 日志在用户自己的时间轴上显示的推文数量创建用户排名。 给出了
整数 K ,因此从上面的排名来看 请输出第 K 个用户的时间线上显示的推文数量。
在初始状态下,假设每个用户没有关注任何人。
入力
N M K
s_{1}
s_{2}
:
:
s_{M}
- 1 行是一个表示用户数量的整数。 N(2≦N≦100,000) ,表示日志中行数的整数 M(0≦M≦100,000) 、整数 K(1≦K≦N) 由半角空格分隔。 跨
- 2 从行 M+1 至行 M 行记录 s_{i}(1≦i≦M) 。 来自行
- 日志 s_{i} 表示 3 它可以分为不同的格式。小于或等于的整数 j 和整数 k 是代表每个用户的数字, (1≦j, k≦N, j ≠ k)有保证。
- s_{i} 的第一个字符是
t什么时候 - s_{i} 的第一个字符是
f什么时候 - s_{i} 的第一个字符是
u什么时候
t j用户 j 的意思是“推文”。
f j k用户 j 是用户 表示您已“关注” k 。 表示您已“取消关注”
u j k用户 j 是用户 表示您已“关注” k 。
出力
请在末尾输出换行符。
入力例 1
5 9 1 t 1 f 1 3 f 2 1 t 2 t 1 u 3 1 t 1 t 5 t 5
出力例 1
4
- 见图a
- 首先,用户 1 发推文。由于此时没有人关注用户 1,因此只有用户 1 可以查看此推文。
- 见图b
- 用户 1 随后关注用户 2 和用户 3。
- 用户 2 发推文。由于用户 1 是唯一关注用户 2 的人,因此该推文将出现在用户 1 和用户 2 的时间线上。
- 用户 1 发推文。由于用户 2 和用户 3 关注了用户 1,因此该推文将显示在用户 1、用户 2 和用户 3 的时间线上。
- 见图c
- 用户 1 在用户 3 取消关注用户 1 后发布推文。该推文已被取消关注,因此仅出现在用户 1 和用户 2 的时间线上。
- 用户 5 随后发了两次推文。此推文仅在用户 5 的时间线上可见。
- 每个用户时间线上最终显示的推文数量为 4 用户 2 3 用户 3 1 用户 4 0 用户 5 2 一。
- 因此,在自己的时间轴上显示推文数量最多的用户是用户1,显示的推文数量是 4 就是答案。 由于除了

入力例 2
5 9 2 t 1 f 1 3 f 2 1 t 2 t 1 u 3 1 t 1 t 5 t 5
出力例 2
3
- K 的值外,输入与输入示例 1 相同,因此您自己的时间轴上显示的推文数量为 2 推文数量最多的用户是用户2,显示的推文数量是 3 。
入力例 3
5 9 3 t 1 f 1 3 f 2 1 t 2 t 1 u 3 1 t 1 t 5 t 5
出力例 3
2
- K 的值外,输入与输入示例 1 相同,因此您自己的时间轴上显示的推文数量为 3 数量最多的用户为用户5,显示推文条数为 2 。
入力例 4
5 9 4 t 1 f 1 3 f 2 1 t 2 t 1 u 3 1 t 1 t 5 t 5
出力例 4
1
- K 的值外,输入与输入示例 1 相同,因此您自己的时间轴上显示的推文数量为 4 推文数量最多的用户是用户 3,显示的推文数量为 1 。
入力例 5
5 9 5 t 1 f 1 3 f 2 1 t 2 t 1 u 3 1 t 1 t 5 t 5
出力例 5
0
- K 的值外,输入与输入示例 1 相同,因此您自己的时间轴上显示的推文数量为 5 最受欢迎的用户是用户 2,并且没有显示任何推文。
入力例 6
4 4 3 t 1 t 2 t 3 t 4
出力例 6
1
- 4 一位用户时间轴上显示的推文总数为 1 所以,K 的值为 对于 1 它们的编号最大为 4 的任何值,要输出的答案是 1 。