{"raw_statement":[{"iden":"statement","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 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.\n\nMax 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.\n\nSince 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?\n\nYou have to determine the winner of the game for all initial positions of the marbles."},{"iden":"input","content":"The first line of input contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 100, ).\n\nThe 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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input\n\n4 4\n1 2 b\n1 3 a\n2 4 c\n3 4 b\n\nOutput\n\nBAAA\nABAA\nBBBA\nBBBB\n\nInput\n\n5 8\n5 3 h\n1 2 c\n3 1 c\n3 2 r\n5 1 r\n4 3 z\n5 4 r\n5 2 h\n\nOutput\n\nBABBB\nBBBBB\nAABBB\nAAABA\nAAAAB"},{"iden":"note","content":"Here's the graph in the first sample test case:\n\nHere's the graph in the second sample test case:\n\n"}],"translated_statement":[{"iden":"statement","content":"正如我们所知，Max 是她朋友们中最棒的电子游戏玩家。她的朋友们嫉妒她的能力，于是创造了一个游戏来证明她并非最擅长游戏。该游戏在一个有向无环图（DAG）上进行，图中有 #cf_span[n] 个顶点和 #cf_span[m] 条边。每条边上都写有一个小写英文字母。\n\nMax 和 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 在偶数回合行动。无法行动的玩家输掉游戏。两个棋子可以在同一时刻位于同一顶点。\n\n由于游戏可能耗时较长，而 Lucas 和 Max 需要集中精力寻找 Dart，他们没有时间亲自玩这个游戏。因此，他们请你判断：如果双方都采取最优策略，谁会赢得游戏？\n\n你需要确定所有初始棋子位置组合下的游戏结果。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 100]）。\n\n接下来的 #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]）。任意两个顶点之间最多只有一条边。保证图是无环的。\n\n请输出 #cf_span[n] 行，每行是一个长度为 #cf_span[n] 的字符串。第 #cf_span[i] 行的第 #cf_span[j] 个字符应为 'A'，表示当 Max 的棋子初始位于顶点 #cf_span[i]、Lucas 的棋子初始位于顶点 #cf_span[j] 时 Max 获胜；否则为 'B'。\n\n第一个样例测试用例中的图如下：\n\n第二个样例测试用例中的图如下：\n\n"},{"iden":"input","content":"输入的第一行包含两个整数 #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]）。任意两个顶点之间最多只有一条边。保证图是无环的。"},{"iden":"output","content":"请输出 #cf_span[n] 行，每行是一个长度为 #cf_span[n] 的字符串。第 #cf_span[i] 行的第 #cf_span[j] 个字符应为 'A'，表示当 Max 的棋子初始位于顶点 #cf_span[i]、Lucas 的棋子初始位于顶点 #cf_span[j] 时 Max 获胜；否则为 'B'。"},{"iden":"examples","content":"输入\n4 4\n1 2 b\n1 3 a\n2 4 c\n3 4 b\n输出\nBAAA\nABAA\nBBBB\nABBB\n\n输入\n5 8\n5 3 h\n1 2 c\n3 1 c\n3 2 r\n5 1 r\n4 3 z\n5 4 r\n5 2 h\n输出\nBABBB\nBBBBB\nAAABB\nAAABA\nAAAAA"},{"iden":"note","content":"第一个样例测试用例中的图如下：\n\n第二个样例测试用例中的图如下：\n\n"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions** \nLet $ G = (V, E) $ be a directed acyclic graph (DAG) with $ |V| = n $, $ |E| = m $. \nEach edge $ (v, u) \\in E $ is labeled with a character $ c \\in \\Sigma $, where $ \\Sigma $ is the set of lowercase English letters. \nLet $ \\text{ord}(c) $ denote the ASCII value of character $ c $. \n\nLet $ (i, j) \\in V \\times V $ denote the initial positions of Max’s and Lucas’s marbles, respectively. \nPlayers alternate turns: Max moves on odd-numbered rounds, Lucas on even-numbered rounds. \nLet $ r \\geq 1 $ denote the global round number (1-indexed). \nLet $ c_r \\in \\Sigma $ denote the character used in round $ r $. \nConstraint: $ \\text{ord}(c_r) \\geq \\text{ord}(c_{r-1}) $ for all $ r \\geq 2 $. \n\nA player loses if they cannot make a valid move on their turn. \n\n**Constraints** \n1. $ 2 \\leq n \\leq 100 $, $ m \\leq \\frac{n(n-1)}{2} $ \n2. $ G $ is acyclic. \n3. For each edge $ (v, u, c) \\in E $, $ 1 \\leq v, u \\leq n $, $ v \\neq u $, $ c \\in \\Sigma $. \n4. At most one edge between any pair of vertices. \n\n**Objective** \nFor each initial state $ (i, j) \\in V \\times V $, determine the winner under optimal play: \n- Output an $ n \\times n $ matrix $ W $, where $ W[i][j] = $ \n - `'A'` if Max wins when starting at $ (i, j) $, \n - `'B'` otherwise. \n\nThe game state is fully described by $ (v, u, \\ell) $, where: \n- $ v \\in V $: Max’s current vertex, \n- $ u \\in V $: Lucas’s current vertex, \n- $ \\ell \\in \\Sigma \\cup \\{ \\bot \\} $: last used character (or $ \\bot $ for no prior move). \n\nDefine $ \\text{win}(v, u, \\ell) \\in \\{ \\text{True}, \\text{False} \\} $: \n- True if the *current player* can force a win from state $ (v, u, \\ell) $. \n- The current player is Max if the number of prior moves is even (i.e., round is odd), Lucas otherwise. \n\nBut since turn order is determined by move count, and the state must encode whose turn it is, we instead define: \n\nLet $ \\text{dp}[v][u][c] $ be a boolean value indicating whether the *current player* wins from state where: \n- Max is at vertex $ v $, \n- Lucas is at vertex $ u $, \n- Last character used is $ c \\in \\Sigma \\cup \\{ \\bot \\} $, \n- The turn is determined implicitly by the number of moves made (which is not stored, so we must encode turn in state). \n\nBut since the parity of moves determines the current player, and the state space is small ($ n \\leq 100 $, $ |\\Sigma| = 26 $), we define: \n\n**State:** $ (v, u, \\ell, p) $, where: \n- $ v, u \\in V $: positions of Max and Lucas, \n- $ \\ell \\in \\Sigma \\cup \\{ \\bot \\} $: last character played ($ \\bot $ for no move yet), \n- $ p \\in \\{0, 1\\} $: player to move (0 = Max, 1 = Lucas). \n\n**Transition:** \nFrom state $ (v, u, \\ell, p) $, the current player $ p $ moves their own marble: \n- If $ p = 0 $: choose edge $ (v, v', c) \\in E $ such that $ \\text{ord}(c) \\geq \\text{ord}(\\ell) $ (if $ \\ell \\neq \\bot $), or any $ c $ if $ \\ell = \\bot $. \n- If $ p = 1 $: choose edge $ (u, u', c) \\in E $ with same constraint. \n\nNew state: \n- If $ p = 0 $: $ (v', u, c, 1) $ \n- If $ p = 1 $: $ (v, u', c, 0) $ \n\n**Base case:** \nIf no valid move exists, current player loses → return False. \n\n**Objective:** \nFor all $ i, j \\in V $: \nCompute $ \\text{dp}[i][j][\\bot][0] $ → if True, output `'A'`; else `'B'`. \n\n**Output:** \nAn $ n \\times n $ matrix where entry $ (i, j) $ is `'A'` if $ \\text{dp}[i][j][\\bot][0] = \\text{True} $, else `'B'`.","simple_statement":null,"has_page_source":false}