AT_tricky_4 高橋くんレーシング

[problemUrl]: https://atcoder.jp/contests/tricky/tasks/tricky_4 高橋くんはレーサーで，`Takahashi`という名前で，合計 $ N $ 人の参加者のいるレースに参加しました． 健気なサポーターである青木くんはラジオで高橋くんが参加しているレースのことを聞いていました． ラジオでは，最初に，スタート直後の全員の順位を発表しました． 青木くんは全ての順位を聞くことはできませんでしたが，高橋くんの順位を聞き取りメモしました． また，その後，ラジオでは誰かが誰かを抜いた時に，それを全て発表しました． 青木くんは全ての誰が誰を抜いたかという情報をメモしました． 青木くんのメモが与えられるので，高橋くんの最終順位を求めて下さい． ただし，青木くんは間違えてメモした可能性もあるので，メモに矛盾があったらそれを指摘してください． 出場しているレーサーの名前は全て異なり，アルファベットの大文字と小文字は区別され別の文字とみなされます． また，抜き去る一瞬を除いて，同じ順位になっているレーサーは $ 2 $ 人以上はいないものとします． 最初の行にはテストケースの数 $ T $ が与えられる． その後の行には $ T $ 個のテストケースが続く． 各テストケースの $ 1 $ 行目には，出場したレーサーの数 $ N $ と，青木くんのメモに含まれる誰が誰を抜いたかという記録の数 $ R $ が与えられます． その次の行には，`Takahashi is the 順位`をいう形の文字列が与えられ，高橋くんのスタート直後の順位を表す． ここで，順位は $ 1 $ 位から順番に`1st place`，`2nd place`，`3rd place`，`4th place`，`5th place`，...となり，$ N+1 $ 位以下を指すことはありません． その後の $ R $ 行には，誰が誰を抜いたかという記録が時系列順に与えられ，各行は`名前1 overtakes 名前2`という形をしている． ここで，`名前1`と`名前2`は半角アルファベットのみからなり，`名前1`の名前のレーサーが`名前2`の名前のレーサーを追い抜いたことを表す． - $ 0\ \leq\ T\ \leq\ 10^4 $ - $ 1\ \leq\ N $ - $ 0\ \leq\ R\ \leq\ 4\ \times\ 10^5 $ - `Takahashi is the 順位`の`順位`は $ 1 $ 位から $ N $ 位までのどれかを指し示す - `名前1`，`名前2`は半角アルファベットのみからなる $ 1 $ 文字以上 $ 20 $ 文字以下の文字列である - $ 1 $ つのテストファイルに含まれる $ R $ の和は $ 4\ \times\ 10^5 $ を超えない 各テストケースに対して，メモに矛盾がある場合は`The memo must be wrong`と出力してください． 矛盾がない場合は，`Takahashi might get the 順位`と出力してください． ここで，`順位`は，入力の項で説明されているものと同じ形式を用い，メモが正しい場合の高橋くんの最終順位を表してください． ``` 2 3 2 Takahashi is the 2nd place Takahashi overtakes Aoki HechoSamurai overtakes Aoki 2 1 Takahashi is the 1st place Takahashi overtakes Aoki ``` ``` Takahashi might get the 1st place The memo must be wrong ``` 入力の形式は，入力の項に書かかれている形式に従います． 例えば，以下の入力は全てinvalidで，テストケースにこのような入力は含まれません． ``` 1 3 0 Takahashikun starts with the 2nd place ``` ``` 1 3 1 Takahashi is the 2nd place Takahashi kicks Aoki ``` ただし，`名前1`と`名前2`が異なるなどとは言及されていないことに注意してください．

N/A

N/A