백년 전쟁

문제 정보

문제

중세 당시 영국과 프랑스는 백여년간 전쟁을 해왔다. 각 국은 전통적인 봉건질서에 따른 봉신관계로 이루어진 국가였다. 초기에는 모든 귀족들이 전통적인 관계를 존중하였으나, 전쟁이 길어지면서 몇몇 귀족이 반란을 일으키고 상대방에 붙는 경우가 있었다. 이 때, 그 귀족에 복종하는 모든 신하들은 그 귀족을 따라 편을 옮긴다. 만약 그 귀족의 수하에 또 다른 영주가 반란을 일으키면(혹은 이미 반란을 일으켰더라면) 그 영주는 다시 그 귀족의 상대국, 즉 자신의 원래 국가로 돌아가게 된다. 예를 들어서 이런 경우가 가능하다:

"폐하, 노르망디 공작이 영국의 편에 붙었습니다. 그러나 걱정 안 하셔도 됩니다. 노르망디 공작에게 반란을 일으키고 영국으로 떠났던 로엔 백작이 다시 우리 프랑스의 편으로 돌아올 테니까요. 다만 로엔 백작에 반란을 일으키고 우리와 동맹을 맺었던 남작은 다시 영국과 동맹을 맺은 것 같습니다.."

또한 반란을 일으켰던 귀족이 다시 원래의 주군에게 항복하는 경우도 생긴다. 이 때 역시 (반란상태가 아닌) 부하 귀족들은 귀족의 편을 따라가고 반란 상태인 부하 귀족들은 상대편 국가로 다시 옮겨 전쟁을 계속 할 것이다.
백 년 가까운 시간이 흐르면서 반란 관계 역시 복잡해졌다. 서로 다른 두 명의 영주가 적인지 아군인지를 판단하는 것도 힘들어졌다. 당신이 할 일은 전통적 봉신 관계와 반란 또는 항복 과정이 입력으로 주어지면, 중간 중간 특정 두 봉건 귀족의 사이가 적인지 아군인지 판단하는 것이다.

입력

첫 줄에는 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에 귀족의 수 N(2 ≤ N ≤ 50,000)과 사건 또는 질문의 개수 Q(1 ≤ Q ≤ 50,000)가 주어진다. 두 번째 줄부터 N - 2 줄에 걸쳐서 하나의 공백으로 구분된 두 개의 숫자 ai,bi(1 ≤ ai ≤ N, 3 ≤ bi ≤ N, 0 ≤ i < N - 2)가 주어진다. 이는 귀족 ai가 귀족 bi의 주군임을 의미한다. 또한 귀족번호 1은 프랑스 왕, 2는 영국 왕을 의미하며 이 둘은 주군을 가지지 않는다.
이 후 Q줄에 걸쳐 'T i' 또는 'Q i j'형식으로 입력이 들어온다. T로 입력이 시작되는 줄은 i(3 ≤ i ≤ N)번 귀족이 반란을 일으켰거나 이미 반란을 일으켰다면 항복을 했음을 의미한다. Q로 입력이 시작되는 줄은 i번 귀족과 j번 귀족이(1 ≤ i,j ≤ N) 적인지 아군인지를 묻는 것이다.

출력

Q줄에 걸쳐 나열된 질문들에 대하여 i번과 j번 귀족이 같은 편이면 “Ally”, 적이면 “Enemy”를 출력한다.

예제 입력

1
5 7
1 3
2 4
3 5
T 5
Q 5 2
T 3
Q 5 2
T 3
Q 5 2
Q 1 2

예제 출력

Ally
Enemy
Ally
Enemy

노트

13개의 댓글이 있습니다.