시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB224784736.434%

문제

n개의 정점으로 이루어진 트리가 있다. 이와 같은 트리를 DFS와 비슷한 방식으로 탐색하려 한다. 탐색을 시작할 때에는 트리의 한 정점에서 시작하여, 한 번도 지나지 않은 간선을 따라서 다음 정점으로 이동한다. 이때 한 번도 지나지 않은 간선이 여러 개 존재한다면 그 중 하나를 임의로 선택한다. 만약 한 번도 지나지 않은 간선이 존재하지 않는다면, 전 단계로 돌아간다. 이와 같은 과정을 반복하면 모든 간선을 두 번씩 지나게 된다.

이와 같은 탐색을 할 때, 시작 정점에서 멀어질 때 0을, 시작 정점에 가까워 질 때 1을 적으면 경로를 얻을 수 있다. 하지만 이와 같은 경로 저장 방식을 사용하면, 같은 트리라 하더라도 여러 개의 경로로 저장될 수 있다.

예를 들어 위와 같은 트리를 살펴보면, 0010011101001011, 0100011011001011, 0100101100100111 등의 경로로 탐색될 수 있다. 탐색 시작 정점은 그림에서 크게 표시된 정점이다.

트리를 탐색한 경로가 두 개 주어졌을 때, 이 경로들이 같은 트리를 탐색한 것인지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 데이터의 개수 T(1 ≤ T ≤ 10)이 주어진다. 다음 2×T개의 줄에는 트리를 탐색한 경로가 주어진다. 경로의 길이는 3,000을 넘지 않는다.

출력

입력 데이터 순서대로 T개의 줄에 출력을 하는데, 만약 같은 트리라면 1을, 다른 트리라면 0을 출력한다.

예제 입력 1

2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

예제 출력 1

1
0
W3sicHJvYmxlbV9pZCI6IjIzNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMgXHVkMGQwXHVjMGM5XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5uXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkMmI4XHViOWFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI5N2MgREZTXHVjNjQwIFx1YmU0NFx1YzJiN1x1ZDU1YyBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVkMGQwXHVjMGM5XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVkMGQwXHVjMGM5XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzU4IFx1ZDU1YyBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjLCBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YzljMFx1YjA5OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWIyZTRcdWM3NGMgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1ZDU1YyBcdWJjODhcdWIzYzQgXHVjOWMwXHViMDk4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNzg0XHVjNzU4XHViODVjIFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1ZDU1YyBcdWJjODhcdWIzYzQgXHVjOWMwXHViMDk4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCwgXHVjODA0IFx1YjJlOFx1YWNjNFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDRcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YmMxOFx1YmNmNVx1ZDU1OFx1YmE3NCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjQ1MCBcdWJjODhcdWM1MjkgXHVjOWMwXHViMDk4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQwZDBcdWMwYzlcdWM3NDQgXHVkNTYwIFx1YjU0YywgXHVjMmRjXHVjNzkxIFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyBcdWJhNDBcdWM1YjRcdWM5YzggXHViNTRjIDBcdWM3NDQsIFx1YzJkY1x1Yzc5MSBcdWM4MTVcdWM4MTBcdWM1ZDAgXHVhYzAwXHVhZTRjXHVjNmNjIFx1YzljOCBcdWI1NGMgMVx1Yzc0NCBcdWM4MDFcdWM3M2NcdWJhNzQgXHVhY2JkXHViODVjXHViOTdjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWI4NWMgXHVjODAwXHVjN2E1IFx1YmMyOVx1YzJkZFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQsIFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI3N2MgXHVkNTU4XHViMzU0XHViNzdjXHViM2M0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVhY2JkXHViODVjXHViODVjIFx1YzgwMFx1YzdhNVx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTAzXC90cmV0cmUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA1cHg7IHdpZHRoOjI4MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHViYTc0LCAwMDEwMDExMTAxMDAxMDExLCAwMTAwMDExMDExMDAxMDExLCAwMTAwMTAxMTAwMTAwMTExIFx1YjRmMVx1Yzc1OCBcdWFjYmRcdWI4NWNcdWI4NWMgXHVkMGQwXHVjMGM5XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDBkMFx1YzBjOSBcdWMyZGNcdWM3OTEgXHVjODE1XHVjODEwXHVjNzQwIFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWQwNmNcdWFjOGMgXHVkNDVjXHVjMmRjXHViNDFjIFx1YzgxNVx1YzgxMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmI4XHViOWFjXHViOTdjIFx1ZDBkMFx1YzBjOVx1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVhY2JkXHViODVjXHViNGU0XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVkMGQwXHVjMGM5XHVkNTVjIFx1YWM4M1x1Yzc3OFx1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMzcwXHVjNzc0XHVkMTMwXHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmxlOyBUICZsZTsgMTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIDImdGltZXM7VFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDBkMFx1YzBjOVx1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjYmRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDMsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVjNzQ0IFx1ZDU1OFx1YjI5NFx1YjM3MCwgXHViOWNjXHVjNTdkIFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI3N2NcdWJhNzQgMVx1Yzc0NCwgXHViMmU0XHViOTc4IFx1ZDJiOFx1YjlhY1x1Yjc3Y1x1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMzc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3Vid2F5IHRyZWUgc3lzdGVtcyIsImRlc2NyaXB0aW9uIjoiPHA+U29tZSBtYWpvciBjaXRpZXMgaGF2ZSBzdWJ3YXkgc3lzdGVtcyBpbiB0aGUgZm9ybSBvZiBhIHRyZWUsIGkuZS4gYmV0d2VlbiBhbnkgcGFpciBvZiBzdGF0aW9ucywgdGhlcmUgaXMgb25lIGFuZCBvbmx5IG9uZSB3YXkgb2YgZ29pbmcgYnkgc3Vid2F5LiBNb3Jlb3ZlciwgbW9zdCBvZiB0aGVzZSBjaXRpZXMgaGF2ZSBhIHVuaXF1ZSBjZW50cmFsIHN0YXRpb24uIEltYWdpbmUgeW91IGFyZSBhIHRvdXJpc3QgaW4gb25lIG9mIHRoZXNlIGNpdGllcyBhbmQgeW91IHdhbnQgdG8gZXhwbG9yZSBhbGwgb2YgdGhlIHN1YndheSBzeXN0ZW0uIFlvdSBzdGFydCBhdCB0aGUgY2VudHJhbCBzdGF0aW9uIGFuZCBwaWNrIGEgc3Vid2F5IGxpbmUgYXQgcmFuZG9tIGFuZCBqdW1wIGFib2FyZCB0aGUgc3Vid2F5IGNhci4gRXZlcnkgdGltZSB5b3UgYXJyaXZlIGF0IGEgc3RhdGlvbiwgeW91IHBpY2sgb25lIG9mIHRoZSBzdWJ3YXkgbGluZXMgeW91IGhhdmUgbm90IHlldCB0cmF2ZWxsZWQgb24uIElmIHRoZXJlIGlzIG5vbmUgbGVmdCB0byBleHBsb3JlIGF0IHlvdXIgY3VycmVudCBzdGF0aW9uLCB5b3UgdGFrZSB0aGUgc3Vid2F5IGxpbmUgYmFjayBvbiB3aGljaCB5b3UgZmlyc3QgY2FtZSB0byB0aGUgc3RhdGlvbiwgdW50aWwgeW91IGV2ZW50dWFsbHkgaGF2ZSB0cmF2ZWxsZWQgYWxvbmcgYWxsIG9mIHRoZSBsaW5lcyB0d2ljZSwgb25jZSBmb3IgZWFjaCBkaXJlY3Rpb24uIEF0IHRoYXQgcG9pbnQgeW91IGFyZSBiYWNrIGF0IHRoZSBjZW50cmFsIHN0YXRpb24uIEFmdGVyd2FyZHMsIGFsbCB5b3UgcmVtZW1iZXIgb2YgdGhlIG9yZGVyIG9mIHlvdXIgZXhwbG9yYXRpb24gaXMgd2hldGhlciB5b3Ugd2VudCBmdXJ0aGVyIGF3YXkgZnJvbSB0aGUgY2VudHJhbCBzdGF0aW9uIG9yIGJhY2sgdG93YXJkcyBpdCBhdCBhbnkgZ2l2ZW4gdGltZSwgaS5lLiB5b3UgY291bGQgZW5jb2RlIHlvdXIgdG91ciBhcyBhIGJpbmFyeSBzdHJpbmcsIHdoZXJlIDAgZW5jb2RlcyB0YWtpbmcgYSBzdWJ3YXkgbGluZSBnZXR0aW5nIHlvdSBvbmUgc3RhdGlvbiBmdXJ0aGVyIGF3YXkgZnJvbSB0aGUgY2VudHJhbCBzdGF0aW9uLCBhbmQgMSBlbmNvZGVzIGdldHRpbmcgeW91IG9uZSBzdGF0aW9uIGNsb3NlciB0byB0aGUgY2VudHJhbCBzdGF0aW9uLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3OXB4OyB3aWR0aDo1ODlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gVG8gdGhlIGxlZnQ6IEEgc3Vid2F5IHRyZWUgc3lzdGVtLiBUaGUgbGFyZ2VyIGRvdCBpcyB0aGUgY2VudHJhbCBzdGF0aW9uLiBUbyB0aGUgcmlnaHQ6IFRocmVlIG91dCBvZiBzZXZlcmFsIHBvc3NpYmxlIGVuY29kaW5ncyBvZiBleHBsb3JhdGlvbiB0b3VycyBmb3IgdGhlIHN1YndheSBzeXN0ZW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiBpbnB1dCBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IHNjZW5hcmlvcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBzY2VuYXJpbyBjb25zaXN0cyBvZiB0d28gbGluZXMsIGVhY2ggY29udGFpbmluZyBhIHN0cmluZyBvZiB0aGUgY2hhcmFjdGVycyAmIzM5OzAmIzM5OyBhbmQgJiMzOTsxJiMzOTsgb2YgbGVuZ3RoIGF0IG1vc3QgMzAwMCwgYm90aCBkZXNjcmliaW5nIGEgY29ycmVjdCBleHBsb3JhdGlvbiB0b3VyIG9mIGEgc3Vid2F5IHRyZWUgc3lzdGVtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3Qgc2NlbmFyaW8sIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSB0ZXh0ICZsZHF1bztzYW1lJnJkcXVvOyBpZiB0aGUgdHdvIHN0cmluZ3MgbWF5IGVuY29kZSBleHBsb3JhdGlvbiB0b3VycyBvZiB0aGUgc2FtZSBzdWJ3YXkgdHJlZSBzeXN0ZW0sIG9yIHRoZSB0ZXh0ICZsZHF1bztkaWZmZXJlbnQmcmRxdW87IGlmIHRoZSB0d28gc3RyaW5ncyBjYW5ub3QgYmUgZXhwbG9yYXRpb24gdG91cnMgb2YgdGhlIHNhbWUgc3Vid2F5IHRyZWUgc3lzdGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=