거짓말 탐지기 (Large)

먼 섬 구글리아에는 도시가 두 곳 있다. 진실 마을(Truthtown) 사람은 언제나 참말만 하고, 거짓 마을(Liarville) 사람은 언제나 거짓말만 한다. 구글리아를 돌아다니다 주민 N명을 만났고, 각자가 어느 도시 출신인지 알아내려고 한다.

주민에게 1번부터 N번까지 번호를 붙인다. 그다음 한 명씩 물어보고, 주민이 한 진술 M개를 아래 약식 표기로 적어 둔다.

주민은 자기 자신을 언급할 수도 있다. 즉 i가 j나 k와 같을 수 있다. 모든 진술과 맞아떨어지는 배정이 적어도 하나는 반드시 존재한다.

주민마다 어느 도시 출신인지 판정하라.

예를 들어 진술이 1 D 2 3, 1 D 2 4, 1 D 3 4, 2 L 1 네 개라면 다음과 같이 추론한다.

• 도시가 두 곳뿐이므로 2번, 3번, 4번이 모두 서로 다른 도시 출신일 수는 없다.
• 그러므로 1번의 진술 중 적어도 하나는 거짓말이다.
• 그러므로 1번은 거짓 마을 출신이고, 1번의 진술은 전부 거짓말이다.
• 그러므로 2번, 3번, 4번은 모두 같은 도시 출신이다.
• 2번의 진술은 참이므로 2번은 진실 마을 출신이다.
• 그러므로 3번과 4번도 진실 마을 출신이다.

첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 테스트 케이스가 T개 주어진다. 각 테스트 케이스의 첫 줄에는 정수 N과 M이 주어진다. 다음 M개의 줄에는 주민 한 명의 진술이 위 표기법으로 한 줄에 하나씩 주어진다.

제한

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 500
• 1 ≤ M ≤ 500
• 1 ≤ i, j, k ≤ N
• j와 k는 서로 다르다

각 테스트 케이스마다 "Case #x: y1 y2 ... yN" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, yi는 i번 주민을 나타내는 문자 하나이다.

• 주어진 진술로 i번이 진실 마을 출신임이 확정되면 T를 출력한다.
• 주어진 진술로 i번이 거짓 마을 출신임이 확정되면 L을 출력한다.
• 주어진 진술만으로는 i번이 두 도시 어느 쪽에서도 왔을 수 있으면 -를 출력한다.

문자 사이는 공백 하나로 구분한다.