C - Chokutter Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

セキュリティに興味がある高橋君は、デジタルアーツ株式会社に就職したい青年です。
彼はいま、自分で運営している「つぶやき型」SNSのログを調べています。
このSNSは「Chokutter」と呼ばれており、一部の競技プログラマの間で大流行しています。
以下で「Chokutter」の仕様を説明します。
  1. 短文を「つぶやく」ことができます。
    • あなたのつぶやきは自分のタイムラインに表示されます。
  2. 自分以外のユーザを「フォロー」することができます。
    • あなたがあるユーザAをフォローすると、以降にユーザAがつぶやいたつぶやきはあなたのタイムラインに表示されるようになります。フォローする前のつぶやきは表示されません。
    • Chokutterでは、あなたがユーザAをフォローすると、システムによって強制的に同時にユーザAもあなたをフォローします。
    • 上記より、あなたとユーザAのタイムラインのそれぞれに、フォロー後のあなたのつぶやきが表示されることに注意してください。
    • 既にフォローをしている人や、自分自身をフォローすることは出来ません。
  3. 自分以外のユーザを「アンフォロー」することができます。
    • あなたがあるユーザAをアンフォローするとフォロー状態が解除され、アンフォロー後のユーザAのつぶやきはあなたのタイムラインに表示されなくなります。もともと見えていたつぶやきは、そのまま表示されています。
    • Chokutterでは、あなたがユーザAをアンフォローすると、システムによって強制的に同時にユーザAもあなたをアンフォローします。
    • 上記より、あなたがアンフォローしたユーザAのタイムラインには、アンフォロー後のあなたのつぶやきが表示されなくなります。
    • フォローをしていない人や、自分自身をアンフォローすることは出来ません。
類似サービスといくつか仕様が異なることにお気をつけ下さい。

高橋君はChokutterログをもとにして、ユーザ自身のタイムラインに表示されているつぶやきの数が多いユーザランキングを作ろうと思いました。
整数 K が与えられるので、そのランキングの上から K 番目にあたるユーザのタイムラインに表示されているつぶやきの数を出力してください。
なお、初期状態では、各ユーザは誰もフォローしていないものとします。

入力

入力は以下の形式で標準入力から与えられる。 
N M K
s_{1}
s_{2}
:
:
s_{M}
  1. 1 行目にはユーザ数を表す整数 N(2≦N≦100,000) 、ログの行数を表す整数 M(0≦M≦100,000) 、整数 K(1≦K≦N) が半角スペース区切りで与えられる。
  2. 2 行目から M+1 行目までの M 行にわたってログ s_{i}(1≦i≦M) が与えられる。
  3. ログ s_{i} は 3 種類の形式に分類することができる。以下の 整数 j と 整数 k はそれぞれユーザを表す番号で、 (1≦j, k≦N, j ≠ k)が保証されている。
    • s_{i} の先頭文字が t のとき
        • t j
        ユーザ j が「つぶやいた」ことを表す。
    • s_{i} の先頭文字が f のとき
        • f j k
        ユーザ j が ユーザ k を「フォロー」したことを表す。
    • s_{i} の先頭文字が u のとき
        • u j k
        ユーザ j が ユーザ k を「アンフォロー」したことを表す。

出力

ユーザ自身のタイムラインに表示されているつぶやきの数が多い順に上から 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をフォローしている人はこの時点で存在しないため、ユーザ1のみがこのつぶやきを閲覧することが出来ます。
  • 図b参照
    1. 次に、ユーザ1が、ユーザ2およびユーザ3をフォローします。
    2. ユーザ2がつぶやきます。ユーザ2をフォローしているのはユーザ1だけなので、ユーザ1とユーザ2のタイムラインにこのつぶやきが表示されます。
    3. ユーザ1がつぶやきます。ユーザ1をフォローしているのはユーザ2とユーザ3なので、ユーザ1、ユーザ2、ユーザ3の3人のタイムラインにこのつぶやきを表示されます。
  • 図c参照
    1. ユーザ3がユーザ1をアンフォローした後、ユーザ1がつぶやきます。このつぶやきはアンフォローが行われたので、ユーザ1とユーザ2の2人のタイムラインにのみ表示されます。
    2. その後、ユーザ5が2回つぶやきます。このつぶやきが表示されるのはユーザ5のタイムラインだけです。
    3. 最終的に各ユーザのタイムラインに表示されたつぶやきの数は、ユーザ1が 4 つ、ユーザ2が 3 つ、ユーザ3が 1 つ、ユーザ4が 0 つ、ユーザ5が 2 つです。
    4. よって、一番自分自身のタイムラインに表示されているつぶやきの数が多いユーザはユーザ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 となります。

Source Name

DigitalArts 2012