MADMAX

우리 모두가 알다시피, Max는 친구들 중에서 비디오 게임을 가장 잘한다. 친구들은 Max를 너무 질투한 나머지, Max가 게임을 가장 잘하는 사람이 아니라는 것을 증명하기 위해 실제 게임을 하나 만들었다. 이 게임은 n개의 정점과 m개의 간선을 가진 방향 비순환 그래프(DAG)에서 진행된다. 각 간선에는 영문 소문자 하나가 적혀 있다.

Max and Lucas이 게임을 한다. Max가 먼저 움직이고, 그다음 Lucas가 움직인 뒤, 다시 Max가 움직이는 식으로 계속된다. 각 플레이어는 구슬 하나를 가지며, 처음에는 어떤 정점에 놓여 있다. 각 플레이어는 자신의 차례에 어떤 간선을 따라 자신의 구슬을 이동해야 한다(v에서 u로 나가는 간선이 있다면 플레이어는 정점 v에서 정점 u로 구슬을 이동할 수 있다). 플레이어가 자신의 구슬을 정점 v에서 정점 u로 이동했다면, 그 라운드의 "character"은 v에서 u로 향하는 간선에 적힌 문자이다. 추가 규칙이 하나 있다. 라운드 i의 문자의 ASCII 코드는 라운드 i의 문자의 ASCII 코드 - 1 이상이어야 한다 (for i > 1). 라운드는 두 플레이어를 합쳐서 번호를 매긴다. 즉, Max는 홀수 번호의 라운드에 움직이고 Lucas는 짝수 번호의 라운드에 움직인다. 이동할 수 없는 플레이어가 게임에서 패배한다. 두 구슬은 동시에 같은 정점에 있을 수도 있다.

게임이 오래 걸릴 수 있고 Lucas and Max은 Dart를 찾는 데 집중해야 하므로, 이들은 게임을 할 시간이 없다. 그래서 두 사람 모두 최적으로 플레이할 경우 누가 게임에서 이기는지 여러분에게 물었다.

구슬의 모든 초기 위치에 대해 게임의 승자를 결정해야 한다.

입력의 첫 번째 줄에는 두 정수 n와 m이 주어진다 (2 ≤ n ≤ 100, ).

다음 m개의 줄에는 간선이 주어진다. 각 줄에는 두 정수 v, u와 영문 소문자 c가 주어지며, 이는 v에서 u로 향하고 c가 적힌 간선이 있다는 뜻이다 (1 ≤ v, u ≤ n, v ≠ u). 임의의 정점 쌍 사이에는 간선이 최대 하나 존재한다. 그래프가 비순환임이 보장된다.

n개의 줄을 출력하며, 각 줄에는 길이가 n인 문자열을 출력한다. i-th번째 줄의 j-th번째 문자는 Max의 구슬이 처음에 정점 i에 있고 Lucas의 구슬이 처음에 정점 j에 있는 경우 Max가 게임에서 이긴다면 'A', 그렇지 않다면 'B'여야 한다.

첫 번째 예제 테스트 케이스의 그래프는 다음과 같다.

두 번째 예제 테스트 케이스의 그래프는 다음과 같다.