시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 12 1 1 100.000%

문제

민승이는 정문이에게 미션을 주면서 즐기고 있다. 정문이는 눈에 헤드밴드를 썼기 때문에 앞을 볼 수 없다.

미션은 1부터 N까지 번호가 붙어진 N개의 컵으로 진행된다. 처음에 민승이는 이 N개의 컵 중 한 컵에 공을 넣는다. (당연히 정문이는 어디에 넣은지 알 수 없다) 그 다음부터 정문이는 매 단계마다 'A' 또는 'B' 문자를 부르고 이에 따라 민승이는 공을 꺼내서 다른 컵으로 넣는다. (꺼내서 다시 동일한 컵에 넣을 수도 있다.) 단 민승이가 공을 꺼내서 넣는 컵은 현재 컵의 위치와 정문이가 부른 알파벳에 의해서만 결정된다.

만약에 현재 공이 K번째 컵에 있다면 이 컵은 정문이가 부른 알파벳에 의해서 Ak(정문이가 'A'를 불렀을 경우) 또는 Bk(정문이가 'B'를 불렀을 경우)번째 컵으로 이동하게 된다.

정문이의 미션은 처음에 민승이가 공을 어떤 컵에 넣든지간에 최종적으로 이 공이 컵 1로 들어가게 하는 것이다. 우리는 이런 정문이를 도와 공이 컵 1로 들어가기 위해 정문이가 불러야할 알파벳 문자열을 찾는것이다. 단, 이 문자열은 10,000보다 작아야 한다.

입력

첫 번째 줄에 컵의 개수 N (1 ≤ N ≤ 500)이 주어진다. 그 다음 N개의 줄에는 한 컵에 대한 Ak와 Bk가 공백으로 구분되어 주어진다. (두 번째 줄에 A1과 B1, 다음 줄에 A2와 B2 등이 주어진다는 뜻이다)

출력

정문이가 불러야할 A또는 B로 구성된 문자열을 출력한다. (여러 해가 존재할 경우에는 그 중 하나만 출력되면 되고 항상 답이 존재하는 입력만 주어진다고 하자.) 문자열의 길이는 10,000보다 작거나 같아야 한다.

예제 입력

4
1 2
1 3
3 1
1 4

예제 출력

ABA

힌트

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Final Exam #1 2번

  • 문제를 번역한 사람: author6
  • 빠진 조건을 찾은 사람: koosaga