CF917B.MADMAX

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.

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.

众所周知，麦克斯是她朋友们中最佳的电子游戏选手。她的朋友们对此十分嫉妒，于是专门设计了一款游戏，试图证明她并非游戏高手。该游戏在一个有向无环图（DAG）上进行，该图包含 $n$ 个顶点和 $m$ 条边。每条边上都标有一个小写英文字母。

麦克斯与卢卡斯正在玩这个游戏。麦克斯先手，接着是卢卡斯，然后是麦克斯，依此类推。每位玩家各持一枚弹珠，初始时位于某个顶点上。在每位玩家的回合中，他/她必须沿某条边移动自己手中的弹珠（即若存在一条从顶点 $v$ 指向顶点 $u$ 的出边，则玩家可将弹珠从 $v$ 移动到 $u$）。若玩家将弹珠从顶点 $v$ 移动到顶点 $u$，则该轮的“字符”即为边 $v \to u$ 上所标注的字符。此外还有一条附加规则：第 $i$ 轮（$i > 1$）的字符的 ASCII 码值必须大于或等于第 $i-1$ 轮字符的 ASCII 码值。轮次编号对两位玩家统一计数，即麦克斯行动在奇数轮，卢卡斯行动在偶数轮。无法进行合法移动的玩家判负。两枚弹珠可以同时位于同一顶点。

由于游戏可能耗时较长，而卢卡斯和麦克斯还需集中精力寻找达特，因此他们没有时间实际游玩。于是他们请你判断：若双方均以最优策略进行游戏，谁将获胜？

你需要对所有可能的弹珠初始位置组合，确定游戏的获胜方。

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.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 100$，）。

接下来的 $m$ 行描述图中的边。每行包含两个整数 $v$、$u$ 和一个小写英文字母 $c$，表示存在一条从顶点 $v$ 指向顶点 $u$ 的有向边，其上标记为字母 $c$（$1 \leq v,\,u \leq n$，且 $v \neq u$）。任意一对顶点之间至多存在一条边。保证该图是无环的。

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.

输出 n 行，每行一个长度为 n 的字符串。第 i 行的第 j 个字符应为 'A'，当且仅当 Max 在其弹珠初始位于顶点 i、Lucas 的弹珠初始位于顶点 j 时能赢得该游戏；否则该字符为 'B'。

Here's the graph in the first sample test case:

Here's the graph in the second sample test case:

第一个样例测试用例中的图：

第二个样例测试用例中的图：