D - 高橋くんレーシング
Editorial
/
21:42追記:R 個のメモは同時刻のものはありません.つまり,同時に 2 回以上誰かが誰かを抜き去るということは起こりません.
高橋くんはレーサーで,
健気なサポーターである青木くんはラジオで高橋くんが参加しているレースのことを聞いていました.
ラジオでは,最初に,スタート直後の全員の順位を発表しました.
青木くんは全ての順位を聞くことはできませんでしたが,高橋くんの順位を聞き取りメモしました.
また,その後,ラジオでは誰かが誰かを抜いた時に,それを全て発表しました.
青木くんは全ての誰が誰を抜いたかという情報をメモしました.
青木くんのメモが与えられるので,高橋くんの最終順位を求めて下さい.
ただし,青木くんは間違えてメモした可能性もあるので,メモに矛盾があったらそれを指摘してください.
出場しているレーサーの名前は全て異なり,アルファベットの大文字と小文字は区別され別の文字とみなされます.
また,抜き去る一瞬を除いて,同じ順位になっているレーサーは 2 人以上はいないものとします.
最初の行にはテストケースの数 T が与えられる.
その後の行には T 個のテストケースが続く.
各テストケースの 1 行目には,出場したレーサーの数 N と,青木くんのメモに含まれる誰が誰を抜いたかという記録の数 R が与えられます.
その次の行には,
ここで,順位は 1 位から順番に
その後の R 行には,誰が誰を抜いたかという記録が時系列順に与えられ,各行は
ここで,
各テストケースに対して,メモに矛盾がある場合は
矛盾がない場合は,
ここで,
入力の形式は,入力の項に書かかれている形式に従います.
例えば,以下の入力は全てinvalidで,テストケースにこのような入力は含まれません.
writer: laycrs
Time Limit: 15 sec / Memory Limit: 256 MB
問題文
Takahashi
という名前で,合計 N 人の参加者のいるレースに参加しました.健気なサポーターである青木くんはラジオで高橋くんが参加しているレースのことを聞いていました.
ラジオでは,最初に,スタート直後の全員の順位を発表しました.
青木くんは全ての順位を聞くことはできませんでしたが,高橋くんの順位を聞き取りメモしました.
また,その後,ラジオでは誰かが誰かを抜いた時に,それを全て発表しました.
青木くんは全ての誰が誰を抜いたかという情報をメモしました.
青木くんのメモが与えられるので,高橋くんの最終順位を求めて下さい.
ただし,青木くんは間違えてメモした可能性もあるので,メモに矛盾があったらそれを指摘してください.
出場しているレーサーの名前は全て異なり,アルファベットの大文字と小文字は区別され別の文字とみなされます.
また,抜き去る一瞬を除いて,同じ順位になっているレーサーは 2 人以上はいないものとします.
入力
その後の行には 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
が異なるなどとは言及されていないことに注意してください.