众所周知,Max 是她朋友中最好的电子游戏玩家。她的朋友们非常嫉妒她,以至于他们创造了一个真正的游戏,只是为了证明她不是最擅长游戏的。该游戏在具有 n 个顶点和 m 个边的有向无环图 (DAG) 上进行。每个边缘都写有一个字符,一个小写英文字母。
Max 和 Lucas 正在玩游戏。麦克斯先行,然后是卢卡斯,然后是麦克斯,依此类推。每个玩家都有一个弹珠,最初位于某个顶点。每个玩家在他/她的回合中应该沿着某个边缘移动他/她的弹珠(如果存在从 v 到 u 的传出边缘,则玩家可以将弹珠从顶点 v 移动到顶点 u)。如果玩家将他/她的弹珠从顶点 v 移动到顶点 u,则该轮的“字符”就是写在从 v 到 u 的边缘上的字符。还有一项附加规则:第 i 轮字符的 ASCII 码应大于或等于第 i - 1 轮字符的 ASCII 码(当 i > 1 时)。双方玩家的回合数一起编号,即。 e.麦克斯(Max)为奇数,卢卡斯(Lucas)为偶数。无法采取行动的玩家输掉游戏。弹珠可能同时位于同一顶点。
由于游戏可能需要一段时间,而卢卡斯和麦克斯必须专注于寻找达特,因此他们没有时间玩。所以他们问你,如果他们都发挥最佳,谁会赢得比赛?
您必须为弹珠的所有初始位置确定游戏的获胜者。
输入
输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 100, $$1 \leq m \leq \frac{n(n-1)}{2}$$)。
接下来的 m 行包含边缘。每行包含两个整数v、u和一个小写英文字母c,表示从v到u有一条边,上面写着c(1≤v,u≤n,v≠u)。任意一对顶点之间至多有一条边。保证该图是非循环的。
输出
打印 n 行,每行一个长度为 n 的字符串。如果 Max 会赢得游戏,并且 Lucas 的弹珠最初位于顶点 i,而 Lucas 的弹珠最初位于顶点 j,则第 i 行中的第 j 个角色应该为“A”,否则为“B”。
示例
输入 #1
4 4 1 2 b 1 3 a 2 4 c 3 4 b
输出 #1
BAAA ABAA BBBA BBBB
输入 #2
5 8 5 3 h 1 2 c 3 1 c 3 2 r 5 1 r 4 3 z 5 4 r 5 2 h
输出 #2
BABBB BBBBB AABBB AAABA AAAAB
注意
这是第一个示例测试用例中的图表:
这是第二个示例测试用例中的图表: