MADMAX

우리 모두가 알다시피, Max는 친구들 중에서 비디오 게임을 가장 잘하는 사람이다. 친구들은 Max를 너무 질투한 나머지, Max가 게임을 가장 잘하는 사람이 아니라는 것을 증명하기 위해 실제 게임까지 만들었다. 이 게임은 n개의 정점과 m개의 간선으로 이루어진 방향 비순환 그래프(a 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'여야 한다.

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

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