English · Original
Chinese · Translation
Formal · Original
As we all know, Max is the best video game player among her friends. Her friends were so jealous of hers, that they created an actual game just to prove that she's not the best at games. The game is played on a directed acyclic graph (a DAG) with _n_ vertices and _m_ edges. There's a character written on each edge, a lowercase English letter.
<center></center>Max and Lucas are playing the game. Max goes first, then Lucas, then Max again and so on. Each player has a marble, initially located at some vertex. Each player in his/her turn should move his/her marble along some edge (a player can move the marble from vertex _v_ to vertex _u_ if there's an outgoing edge from _v_ to _u_). If the player moves his/her marble from vertex _v_ to vertex _u_, the "character" of that round is the character written on the edge from _v_ to _u_. There's one additional rule; the ASCII code of character of round _i_ should be **greater than or equal** to the ASCII code of character of round _i_ - 1 (for _i_ > 1). The rounds are numbered for both players together, i. e. Max goes in odd numbers, Lucas goes in even numbers. The player that can't make a move loses the game. The marbles may be at the same vertex at the same time.
Since the game could take a while and Lucas and Max have to focus on finding Dart, they don't have time to play. So they asked you, if they both play optimally, who wins the game?
You have to determine the winner of the game for all initial positions of the marbles.
## Input
The first line of input contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 100, ).
The next _m_ lines contain the edges. Each line contains two integers _v_, _u_ and a lowercase English letter _c_, meaning there's an edge from _v_ to _u_ written _c_ on it (1 ≤ _v_, _u_ ≤ _n_, _v_ ≠ _u_). There's at most one edge between any pair of vertices. It is guaranteed that the graph is acyclic.
## Output
Print _n_ lines, a string of length _n_ in each one. The _j_\-th character in _i_\-th line should be 'A' if Max will win the game in case her marble is initially at vertex _i_ and Lucas's marble is initially at vertex _j_, and 'B' otherwise.
[samples]
## Note
Here's the graph in the first sample test case:
<center></center>Here's the graph in the second sample test case:
<center></center>
正如我们所知，Max 是她朋友们中最好的视频游戏玩家。她的朋友们嫉妒她，于是创造了一个实际的游戏来证明她并非最擅长游戏。这个游戏在一个有 #cf_span[n] 个顶点和 #cf_span[m] 条边的有向无环图（DAG）上进行。每条边上都写有一个小写英文字母。
Max 和 Lucas 正在玩这个游戏。Max 先手，然后是 Lucas，接着又是 Max，依此类推。每个玩家都有一个棋子，初始时位于某个顶点。每个玩家在自己的回合中必须沿着某条边移动自己的棋子（如果玩家可以从顶点 #cf_span[v] 移动到顶点 #cf_span[u]，当且仅当存在一条从 #cf_span[v] 到 #cf_span[u] 的出边）。当玩家将棋子从顶点 #cf_span[v] 移动到顶点 #cf_span[u] 时，该轮的“字符”就是该边上写的字符。还有一个额外规则：第 #cf_span[i] 轮的字符的 ASCII 码必须 *大于或等于* 第 #cf_span[i - 1] 轮的字符的 ASCII 码（对于 #cf_span[i > 1]）。轮次编号是为两名玩家共同计算的，即 Max 在奇数轮次行动，Lucas 在偶数轮次行动。无法行动的玩家输掉游戏。两个棋子可以在同一时刻位于同一顶点。
由于游戏可能耗时较长，而 Lucas 和 Max 需要集中精力寻找 Dart，他们没有时间亲自玩这个游戏。因此，他们请你帮忙：如果双方都采取最优策略，谁会赢得游戏？
你需要确定所有初始棋子位置下的游戏结果。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 100]）。
接下来的 #cf_span[m] 行包含边的信息。每行包含两个整数 #cf_span[v]、#cf_span[u] 和一个小写英文字母 #cf_span[c]，表示存在一条从 #cf_span[v] 到 #cf_span[u] 的边，边上写有字符 #cf_span[c]（#cf_span[1 ≤ v, u ≤ n]，#cf_span[v ≠ u]）。任意两个顶点之间至多有一条边。保证图是无环的。
输出 #cf_span[n] 行，每行是一个长度为 #cf_span[n] 的字符串。第 #cf_span[i] 行的第 #cf_span[j] 个字符应为 'A'，表示当 Max 的棋子初始位于顶点 #cf_span[i]、Lucas 的棋子初始位于顶点 #cf_span[j] 时 Max 获胜；否则为 'B'。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 100]）。接下来的 #cf_span[m] 行包含边的信息。每行包含两个整数 #cf_span[v]、#cf_span[u] 和一个小写英文字母 #cf_span[c]，表示存在一条从 #cf_span[v] 到 #cf_span[u] 的边，边上写有字符 #cf_span[c]（#cf_span[1 ≤ v, u ≤ n]，#cf_span[v ≠ u]）。任意两个顶点之间至多有一条边。保证图是无环的。
## Output
输出 #cf_span[n] 行，每行是一个长度为 #cf_span[n] 的字符串。第 #cf_span[i] 行的第 #cf_span[j] 个字符应为 'A'，表示当 Max 的棋子初始位于顶点 #cf_span[i]、Lucas 的棋子初始位于顶点 #cf_span[j] 时 Max 获胜；否则为 'B'。
[samples]
## Note
第一个样例的图如下：
第二个样例的图如下：
**Definitions**
Let $ G = (V, E) $ be a directed acyclic graph with $ |V| = n $, $ |E| = m $.
Each edge $ (v, u) \in E $ is labeled with a character $ c \in \Sigma $, where $ \Sigma $ is the set of lowercase English letters.
Let $ \text{ord}(c) $ denote the ASCII value of character $ c $.
Let the game state be a tuple $ (p, q, \ell, t) $, where:
- $ p \in V $: position of Max’s marble,
- $ q \in V $: position of Lucas’s marble,
- $ \ell \in \Sigma \cup \{ \bot \} $: last character played ($ \bot $ for no prior move),
- $ t \in \{0, 1\} $: turn indicator ($ 0 $ for Max, $ 1 $ for Lucas).
**Constraints**
1. $ 2 \le n \le 100 $, $ m \le \frac{n(n-1)}{2} $
2. $ G $ is acyclic.
3. On turn $ i $, if $ i > 1 $, the character $ c_i $ on the chosen edge must satisfy $ \text{ord}(c_i) \ge \text{ord}(c_{i-1}) $.
4. A player loses if they cannot make a valid move.
5. Players alternate turns, Max starts first ($ t = 0 $).
**Objective**
For each initial state $ (i, j, \bot, 0) $ with $ i, j \in V $, determine the winner under optimal play:
- Output an $ n \times n $ matrix $ W $, where
$$
W[i][j] =
\begin{cases}
\texttt{'A'} & \text{if Max wins from } (i, j, \bot, 0) \\
\texttt{'B'} & \text{otherwise}
\end{cases}
$$
API Response (JSON)
{
"problem": {
"name": "B. MADMAX",
"description": {
"content": "As we all know, Max is the best video game player among her friends. Her friends were so jealous of hers, that they created an actual game just to prove that she's not the best at games. The game is p",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF917B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "As we all know, Max is the best video game player among her friends. Her friends were so jealous of hers, that they created an actual game just to prove that she's not the best at games. The game is p...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "正如我们所知，Max 是她朋友们中最好的视频游戏玩家。她的朋友们嫉妒她，于是创造了一个实际的游戏来证明她并非最擅长游戏。这个游戏在一个有 #cf_span[n] 个顶点和 #cf_span[m] 条边的有向无环图（DAG）上进行。每条边上都写有一个小写英文字母。\n\nMax 和 Lucas 正在玩这个游戏。Max 先手，然后是 Lucas，接着又是 Max，依此类推。每个玩家都有一个棋子，初始时位于...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be a directed acyclic graph with $ |V| = n $, $ |E| = m $. \nEach edge $ (v, u) \\in E $ is labeled with a character $ c \\in \\Sigma $, where $ \\Sigma $ is the set o...",
"is_translate": false,
"language": "Formal"
}
]
}