说明

伊朗哈兹菲杯（Hazfi Cup）是一项每年以淘汰赛形式组织的足球锦标赛；即每场比赛的输家立即被淘汰出锦标赛，胜者则进入下一轮比赛。每年，有 $2^k$ 支球队参加这项锦标赛（$k$ 为正整数）。所有球队从第一轮开始比赛，每轮过后，仍在锦标赛中的球队有一半被淘汰。第 $k$ 轮是决赛轮，两支球队争夺冠军。总共进行 $2^k-1$ 场比赛。

哈兹菲杯的锦标赛对阵表在抽签仪式上由特邀嘉宾在场预先确定。它决定了哪些球队在第一轮相遇，以及如果他们晋级到后续轮次，可能会遇到哪些其他球队。具体来说，在抽签仪式上，所有 $2^k$ 支球队被随机分配到第一轮的位置 $1, 2,\ldots , 2^k$，如图中 $k = 3$ 所示。

:::align{center} :::

伊朗足球联合会必须开始组织 2023 年哈兹菲杯。由于今年许多特邀嘉宾可能拒绝出席抽签仪式，联合会决定使用与 2022 年哈兹菲杯相同的锦标赛对阵表。不幸的是，去年的锦标赛对阵表已不可用，但去年锦标赛的所有比赛结果以任意顺序提供。可以证明，锦标赛对阵表可以从这些比赛结果中唯一确定。你的任务是从 2022 年哈兹菲杯的比赛结果中恢复锦标赛对阵表，以便回答球迷们今年常见的以下问题：

• 两支球队 $A$ 和 $B$ 可能在哪个轮次相遇？

输入格式

输入的第一行包含两个空格分隔的整数 $k$，表示锦标赛的轮次数（$1 \leqslant k \leqslant 10$），和 $n$，表示球迷问题的数量（$1 \leqslant n \leqslant 1000$）。接下来 $2^k-1$ 行是 2022 年哈兹菲杯的比赛结果；每行一个结果。每场比赛结果的形式如下：

• $\texttt{teamA}\ g_A\ \texttt{-}\ g_B\ \texttt{teamB}$

其中 $\texttt{teamA}$ 和 $\texttt{teamB}$ 是不同的、由小写英文字母组成的非空字符串，长度最多为 $100$，$g_A$ 和 $g_B$ 分别表示 $\texttt{teamA}$ 和 $\texttt{teamB}$ 的进球数（$g_A\neq g_B$）。在平局的情况下，通过点球大战决定胜者，比赛结果的形式如下：

• $\texttt{teamA}\ g(p_A)\ \texttt{-}\ g(p_B)\ \texttt{teamB}$

其中 $g$ 是每支球队在常规比赛中的进球数，$p_A$ 和 $p_B$ 分别表示 $\texttt{teamA}$ 和 $\texttt{teamB}$ 在点球大战中的进球数（$p_A\neq p_B$）。进球数（即 $g_A$, $g_B$, $g$, $p_A$, $p_B$）都是小于 $100$ 的非负整数。注意，输入中表示比赛结果的每行恰好包含 $4$ 个空格字符。

输入以 $n$ 个查询结束。每个查询在单独一行中给出，包含两个不同的球队名称，由一个空格字符分隔。

输出格式

对于输入中的每个查询，在输出的单独一行中打印一个整数作为答案。

2 3
perspolis 1(4)- 1(3) esteghlal
sepahan 0- 2 perspolis
esteghlal 4(1)- 4(0) shamoshak
shamoshak sepahan
shamoshak perspolis
esteghlal shamoshak

2
2
1

提示

翻译由 DeepSeek V3.2 完成