D - 高橋くんレーシング Editorial /

Time Limit: 15 sec / Memory Limit: 256 MB

21:42追記：R 個のメモは同時刻のものはありません．つまり，同時に 2 回以上誰かが誰かを抜き去るということは起こりません．

問題文

高橋くんはレーサーで，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 < 2^{64}
  • 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が異なるなどとは言及されていないことに注意してください．
writer: laycrs