트리 탐색 경로 비교

정점 n개로 이루어진 트리가 있다. 시작 정점 하나를 정한 뒤, 다음 규칙으로 모든 간선을 탐색한다.

• 아직 지나지 않은 간선을 따라 다음 정점으로 이동한다.
• 선택할 수 있는 간선이 여러 개라면 그중 하나를 임의로 고른다.
• 현재 정점에서 더 이상 지나지 않은 간선이 없으면 직전 정점으로 돌아간다.

이 과정을 끝내면 모든 간선을 정확히 두 번 지나게 된다. 시작 정점에서 더 멀어지는 이동은 0, 시작 정점에 가까워지는 이동은 1로 기록한다. 같은 트리라도 간선을 선택하는 순서가 다르면 서로 다른 문자열로 기록될 수 있다.

두 탐색 문자열이 주어질 때, 두 문자열이 같은 시작 정점을 가진 같은 트리에서 나올 수 있는지 판단하라.

첫째 줄에 데이터 개수 T가 주어진다. (1 ≤ T ≤ 10)

이후 2×T개의 줄에 탐색 문자열이 한 줄에 하나씩 주어진다. 각 문자열의 길이는 3,000을 넘지 않으며, 문자는 0과 1로만 이루어진다. 길이가 0인 문자열은 간선이 없는 트리를 뜻한다.

각 데이터마다 두 문자열이 같은 트리를 나타낼 수 있으면 1, 아니면 0을 입력 순서대로 한 줄에 하나씩 출력한다.