사과나무

사과나무는 루트가 있는 트리이며, 각 정점에는 사과가 하나씩 있다. 자식이 있는 모든 내부 정점은 자식을 두 개 이상 가진다.

벌레는 루트에서 DFS 순서로 트리를 탐색한다. 한 정점의 자식이 여러 개라면 그림에서 왼쪽에 있는 자식부터 방문한다. 새 정점을 처음 방문할 때는 0을 기록하고, 그 정점의 모든 자식을 방문한 뒤 되돌아갈 때는 1을 기록한다. 이렇게 길이 2N인 이진 문자열이 만들어진다.

각 위치의 숫자는 하나의 정점에 대응한다. 0은 그때 처음 방문한 정점에 대응하고, 1은 되돌아가기 직전의 정점에 대응한다. 한 탐색 기록은 다음처럼 나타날 수 있다.

어떤 정점을 잘라 내면 그 정점과 모든 자손 정점이 함께 제거된다. 썩은 사과가 있는 두 위치가 주어졌을 때, 정확히 한 정점을 잘라 두 썩은 사과를 모두 제거해야 한다. 동시에 제거되는 멀쩡한 사과의 수는 가능한 한 적어야 한다.

자를 정점의 방문 위치와 되돌아가는 위치를 구하라.

첫째 줄에 정점 수 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에 벌레가 만든 길이 2N의 이진 문자열이 주어진다.

셋째 줄에 두 정수 X, Y가 주어진다. 이는 이진 문자열의 X번째 숫자에 대응하는 정점과 Y번째 숫자에 대응하는 정점의 사과가 썩었다는 뜻이다. 두 위치가 같은 정점을 가리킬 수도 있다.

잘라야 할 정점을 Z라고 하자. Z를 처음 방문할 때 기록된 0의 위치를 i, Z에서 되돌아갈 때 기록된 1의 위치를 j라고 할 때, 첫째 줄에 i j를 출력한다.