← 返回题目列表

AtCoder · tricky_4

D. 高桥君赛车

中文机器翻译题面 查看原题
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

注意

输入的格式应遵循输入项中所述的格式。
例如,以下所有输入都是无效的,这类输入不会包含在测试用例中。
1
3 0
Takahashikun starts with the 2nd place
1
3 1
Takahashi is the 2nd place
Takahashi kicks Aoki
但是,名前1和 按字典顺序比较名前2请注意,并未提及例如不同等情况。

作者:laycrs 一组