시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 7 6 85.714%

문제

두 바이너리 트리 A와 B는 다음과 같은 두 조건을 만족할 때 동등하다고 한다.

1. 두 트리가 비어있다. 또는,

2. 두 트리의 루트가 같다. 또:

(a) A의 왼쪽 서브 트리가 B의 왼쪽 서브 트리와 동등하고, A의 오른쪽 서브 트리가 B의 오른쪽 서브 트리와 동등하다. 또는,

(b) A의 왼쪽 서브 트리가 B의 오른쪽 서브 트리와 동등하고, A의 오른쪽 서브 트리가 B의 왼쪽 서브 트리와 동등하다.

예를 들어, 아래 왼쪽 3개 트리는 서로 동등하다. 하지만, 가장 오른쪽 트리와는 동등하지 않다.

두 바이너리 트리가 주어졌을 때, 동등한지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 각 줄은 비교해야 하는 트리의 정보이다.

각 트리의 정보는 포스트오더로 주어진다. 서브트리가 없는 경우에는 nil로 주어진다. 트리의 모든 데이터는 알파벳 대문자이다. 각 줄의 마지막은 end가 있다. 예를 들어, 문제 설명의 가장 왼쪽 그림을 포스트오더로 나타내면 다음과 같다.

nil nil nil G F nil nil C nil nil E nil D B A end

출력

각 테스트 케이스에 대해서, 두 트리가 동등하면 true를, 아니면 false를 출력한다.

예제 입력 1

2
nil nil nil G F nil nil C nil nil E nil D B A end
nil nil C nil nil E nil D B nil nil G nil F A end
nil nil nil E D nil nil C B nil nil nil G F A end
nil nil nil E C nil nil D B nil nil nil G F A end

예제 출력 1

true
false
W3sicHJvYmxlbV9pZCI6IjQ5MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyNzRcdWQxMzRcdWM3NTggXHVjMGFjXHVhY2ZjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWI0NTAgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDJiOFx1YjlhYyBBXHVjNjQwIEJcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWI0NTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGMgXHViM2Q5XHViNGYxXHVkNTU4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MS4gXHViNDUwIFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YjYxMFx1YjI5NCw8XC9wPlxyXG48cD5cclxuXHQyLiBcdWI0NTAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWFjMTlcdWIyZTQuIFx1YjYxMDo8XC9wPlxyXG48cD4oYSkgQVx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1YWMwMCBCXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNjQwIFx1YjNkOVx1YjRmMVx1ZDU1OFx1YWNlMCwgQVx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1YWMwMCBCXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNjQwIFx1YjNkOVx1YjRmMVx1ZDU1OFx1YjJlNC4gXHViNjEwXHViMjk0LDxcL3A+XHJcbjxwPihiKSBBXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVhYzAwIEJcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM2NDAgXHViM2Q5XHViNGYxXHVkNTU4XHVhY2UwLCBBXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVhYzAwIEJcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM2NDAgXHViM2Q5XHViNGYxXHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OTggXHVjNjdjXHVjYWJkIDNcdWFjMWMgXHVkMmI4XHViOWFjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIzZDlcdWI0ZjFcdWQ1NThcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWQyYjhcdWI5YWNcdWM2NDBcdWIyOTQgXHViM2Q5XHViNGYxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmVlKDEpLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDQ2N3B4OyBoZWlnaHQ6IDE1NHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIzZDlcdWI0ZjFcdWQ1NWNcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWJlNDRcdWFkNTBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWQyYjhcdWI5YWNcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFx1ZDNlY1x1YzJhNFx1ZDJiOFx1YzYyNFx1YjM1NFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YWMwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IG5pbFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVjNzQwIGVuZFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDQgXHVkM2VjXHVjMmE0XHVkMmI4XHVjNjI0XHViMzU0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRuaWwgbmlsIG5pbCBHIEYgbmlsIG5pbCBDIG5pbCBuaWwgRSBuaWwgRCBCIEEgZW5kPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWI0NTAgXHVkMmI4XHViOWFjXHVhYzAwIFx1YjNkOVx1YjRmMVx1ZDU1OFx1YmE3NCB0cnVlXHViOTdjLCBcdWM1NDRcdWIyYzhcdWJhNzQgZmFsc2VcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ5MzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOZXd0b25cdTIwMTlzIEFwcGxlIiwiZGVzY3JpcHRpb24iOiI8cD5Ud28gYmluYXJ5IHRyZWVzIChjYWxsZWQgQSBhbmQgQikgYXJlIGVxdWl2YWxlbnQgaWYgYW5kIG9ubHkgaWYgb25lIG9mIHRoZSBmb2xsb3dpbmcgdHdvIGNvbmRpdGlvbnMgaG9sZHM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+Qm90aCB0cmVlcyBhcmUgZW1wdHkuIE9yLDxcL2xpPlxyXG5cdDxsaT5UaGUgcm9vdCBub2RlcyBvZiBib3RoIHRyZWVzIGFyZSBlcXVhbCwgYW5kIGVpdGhlcjpcclxuXHQ8b2wgc3R5bGU9XCJsaXN0LXN0eWxlLXR5cGU6bG93ZXItYWxwaGFcIj5cclxuXHRcdDxsaT50aGUgbGVmdCBzdWJ0cmVlIG9mIEEgaXMgZXF1aXZhbGVudCB0byB0aGUgbGVmdCBzdWJ0cmVlIG9mIEIsIGFuZCB0aGUgcmlnaHQgc3VidHJlZSBvZiBBIGlzIGVxdWl2YWxlbnQgdG8gdGhlIHJpZ2h0IHN1YnRyZWUgb2YgQi4gT3IsPFwvbGk+XHJcblx0XHQ8bGk+dGhlIGxlZnQgc3VidHJlZSBvZiBBIGlzIGVxdWl2YWxlbnQgdG8gdGhlIHJpZ2h0IHN1YnRyZWUgb2YgQiwgYW5kIHRoZSByaWdodCBzdWJ0cmVlIG9mIEEgaXMgZXF1aXZhbGVudCB0byB0aGUgbGVmdCBzdWJ0cmVlIG9mIEIuPFwvbGk+XHJcblx0PFwvb2w+XHJcblx0PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSB0aHJlZSB0cmVlcyBvbiB0aGUgbGVmdCBvZiB0aGUgZm9sbG93aW5nIFx1ZmIwMWd1cmUgYXJlIGFsbCBlcXVpdmFsZW50IHRvIGVhY2ggb3RoZXIgYnV0IG5vbmUgaXMgZXF1aXZhbGVudCB0byB0aGUgcmlnaHQtbW9zdCB0cmVlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyZWUoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU0cHg7IHdpZHRoOjQ2N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgaWYgdHdvIGdpdmVuIGJpbmFyeSB0cmVlcyBhcmUgZXF1aXZhbGVudCBvciBub3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gYSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIEQgd2hpY2ggcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpXHVmYjAxZWQgb24gdHdvIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgc3BlY2lcdWZiMDFlcyB0aGUgXHVmYjAxcnN0IHRyZWUsIHdpdGggdGhlIHNlY29uZCB0cmVlIHNwZWNpXHVmYjAxZWQgb24gdGhlIHNlY29uZCBsaW5lLiBFYWNoIHRyZWUgaXMgc3BlY2lcdWZiMDFlZCB1c2luZyBhIGxlZnQtdG8tcmlnaHQgcG9zdFx1ZmIwMXggbm90YXRpb24gd2hlcmUgZWFjaCBlbXB0eSBzdWJ0cmVlIGlzIGV4cGxpY2l0bHkgc3BlY2lcdWZiMDFlZCB1c2luZyB0aGUga2V5d29yZCBuaWwuIEFsbCBkYXRhIGluIHRoZSB0cmVlIGFyZSB1cHBlci1jYXNlIGxldHRlcnMuIFRoZSBlbmQgb2YgdGhlIGxpbmUgaXMgc3BlY2lcdWZiMDFlZCB1c2luZyB0aGUga2V5d29yZCBlbmQuIEZvciBleGFtcGxlLCB0aGUgdHJlZSBvbiB0aGUgbGVmdCBvZiB0aGUgXHVmYjAxZ3VyZSBpcyBzcGVjaVx1ZmIwMWVkIGFzOjxcL3A+XHJcblxyXG48cHJlPlxyXG5uaWwgbmlsIG5pbCBHIEYgbmlsIG5pbCBDIG5pbCBuaWwgRSBuaWwgRCBCIEEgZW5kPFwvcHJlPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IG9uIGEgc2VwYXJhdGUgbGluZSwgdGhlIHdvcmQgJnF1b3Q7dHJ1ZSZxdW90OyBpZiB0aGUgdHdvIHRyZWVzIGFyZSBlcXVpdmFsZW50LiBPdGhlcndpc2UgcHJpbnQgJnF1b3Q7ZmFsc2UmcXVvdDsuPFwvcD5cclxuXHJcbjxwPlRoZSB0d28gdGVzdCBjYXNlcyBpbiB0aGUgZm9sbG93aW5nIHNhbXBsZSBJXC9PIHJlcHJlc2VudCB0aGUgZm91ciB0cmVlcyBkcmF3biBvbiB0aGUgcHJldmlvdXMgcGFnZSAoZnJvbSBsZWZ0IHRvIHJpZ2h0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==