시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 37 9 6 37.500%

문제

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
W3sicHJvYmxlbV9pZCI6IjIzNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMgXHVkMGQwXHVjMGM5XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5uXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkMmI4XHViOWFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI5N2MgREZTXHVjNjQwIFx1YmU0NFx1YzJiN1x1ZDU1YyBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVkMGQwXHVjMGM5XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVkMGQwXHVjMGM5XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzU4IFx1ZDU1YyBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjLCBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YzljMFx1YjA5OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWIyZTRcdWM3NGMgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YyBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YzljMFx1YjA5OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1YWRmOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1Yzc4NFx1Yzc1OFx1Yjg1YyBcdWMxMjBcdWQwZGRcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YzljMFx1YjA5OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQsIFx1YzgwNCBcdWIyZThcdWFjYzRcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzA0XHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWJjMThcdWJjZjVcdWQ1NThcdWJhNzQgXHViYWE4XHViNGUwIFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWI0NTAgXHViYzg4XHVjNTI5IFx1YzljMFx1YjA5OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkMGQwXHVjMGM5XHVjNzQ0IFx1ZDU2MCBcdWI1NGMsIFx1YzJkY1x1Yzc5MSBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgXHViYTQwXHVjNWI0XHVjOWM4IFx1YjU0YyAwXHVjNzQ0LCBcdWMyZGNcdWM3OTEgXHVjODE1XHVjODEwXHVjNWQwIFx1YWMwMFx1YWU0Y1x1YzZjYyBcdWM5YzggXHViNTRjIDFcdWM3NDQgXHVjODAxXHVjNzNjXHViYTc0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2JkXHViODVjIFx1YzgwMFx1YzdhNSBcdWJjMjlcdWMyZGRcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHViYTc0LCBcdWFjMTlcdWM3NDAgXHVkMmI4XHViOWFjXHViNzdjIFx1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yjg1YyBcdWM4MDBcdWM3YTVcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwM1wvdHJldHJlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwNXB4OyB3aWR0aDoyODBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkMmI4XHViOWFjXHViOTdjIFx1YzBiNFx1ZDNiNFx1YmNmNFx1YmE3NCwgMDAxMDAxMTEwMTAwMTAxMSwgMDEwMDAxMTAxMTAwMTAxMSwgMDEwMDEwMTEwMDEwMDExMSBcdWI0ZjFcdWM3NTggXHVhY2JkXHViODVjXHViODVjIFx1ZDBkMFx1YzBjOVx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQwZDBcdWMwYzkgXHVjMmRjXHVjNzkxIFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVkMDZjXHVhYzhjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWM4MTVcdWM4MTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWQwZDBcdWMwYzlcdWQ1NWMgXHVhY2JkXHViODVjXHVhYzAwIFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YWNiZFx1Yjg1Y1x1YjRlNFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDBkMFx1YzBjOVx1ZDU1YyBcdWFjODNcdWM3NzhcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgxJmxlO1QmbGU7MTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIDImdGltZXM7VFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDBkMFx1YzBjOVx1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjYmRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDMsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVjNzQ0IFx1ZDU1OFx1YjI5NFx1YjM3MCwgXHViOWNjXHVjNTdkIFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI3N2NcdWJhNzQgMVx1Yzc0NCwgXHViMmU0XHViOTc4IFx1ZDJiOFx1YjlhY1x1Yjc3Y1x1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMzc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3Vid2F5IHRyZWUgc3lzdGVtcyIsImRlc2NyaXB0aW9uIjoiPHA+U29tZSBtYWpvciBjaXRpZXMgaGF2ZSBzdWJ3YXkgc3lzdGVtcyBpbiB0aGUgZm9ybSBvZiBhIHRyZWUsIGkuZS4gYmV0d2VlbiBhbnkgcGFpciBvZiBzdGF0aW9ucywgdGhlcmUgaXMgb25lIGFuZCBvbmx5IG9uZSB3YXkgb2YgZ29pbmcgYnkgc3Vid2F5LiBNb3Jlb3ZlciwgbW9zdCBvZiB0aGVzZSBjaXRpZXMgaGF2ZSBhIHVuaXF1ZSBjZW50cmFsIHN0YXRpb24uIEltYWdpbmUgeW91IGFyZSBhIHRvdXJpc3QgaW4gb25lIG9mIHRoZXNlIGNpdGllcyBhbmQgeW91IHdhbnQgdG8gZXhwbG9yZSBhbGwgb2YgdGhlIHN1YndheSBzeXN0ZW0uIFlvdSBzdGFydCBhdCB0aGUgY2VudHJhbCBzdGF0aW9uIGFuZCBwaWNrIGEgc3Vid2F5IGxpbmUgYXQgcmFuZG9tIGFuZCBqdW1wIGFib2FyZCB0aGUgc3Vid2F5IGNhci4gRXZlcnkgdGltZSB5b3UgYXJyaXZlIGF0IGEgc3RhdGlvbiwgeW91IHBpY2sgb25lIG9mIHRoZSBzdWJ3YXkgbGluZXMgeW91IGhhdmUgbm90IHlldCB0cmF2ZWxsZWQgb24uIElmIHRoZXJlIGlzIG5vbmUgbGVmdCB0byBleHBsb3JlIGF0IHlvdXIgY3VycmVudCBzdGF0aW9uLCB5b3UgdGFrZSB0aGUgc3Vid2F5IGxpbmUgYmFjayBvbiB3aGljaCB5b3UgZmlyc3QgY2FtZSB0byB0aGUgc3RhdGlvbiwgdW50aWwgeW91IGV2ZW50dWFsbHkgaGF2ZSB0cmF2ZWxsZWQgYWxvbmcgYWxsIG9mIHRoZSBsaW5lcyB0d2ljZSwgb25jZSBmb3IgZWFjaCBkaXJlY3Rpb24uIEF0IHRoYXQgcG9pbnQgeW91IGFyZSBiYWNrIGF0IHRoZSBjZW50cmFsIHN0YXRpb24uIEFmdGVyd2FyZHMsIGFsbCB5b3UgcmVtZW1iZXIgb2YgdGhlIG9yZGVyIG9mIHlvdXIgZXhwbG9yYXRpb24gaXMgd2hldGhlciB5b3Ugd2VudCBmdXJ0aGVyIGF3YXkgZnJvbSB0aGUgY2VudHJhbCBzdGF0aW9uIG9yIGJhY2sgdG93YXJkcyBpdCBhdCBhbnkgZ2l2ZW4gdGltZSwgaS5lLiB5b3UgY291bGQgZW5jb2RlIHlvdXIgdG91ciBhcyBhIGJpbmFyeSBzdHJpbmcsIHdoZXJlIDAgZW5jb2RlcyB0YWtpbmcgYSBzdWJ3YXkgbGluZSBnZXR0aW5nIHlvdSBvbmUgc3RhdGlvbiBmdXJ0aGVyIGF3YXkgZnJvbSB0aGUgY2VudHJhbCBzdGF0aW9uLCBhbmQgMSBlbmNvZGVzIGdldHRpbmcgeW91IG9uZSBzdGF0aW9uIGNsb3NlciB0byB0aGUgY2VudHJhbCBzdGF0aW9uLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3OXB4OyB3aWR0aDo1ODlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gVG8gdGhlIGxlZnQ6IEEgc3Vid2F5IHRyZWUgc3lzdGVtLiBUaGUgbGFyZ2VyIGRvdCBpcyB0aGUgY2VudHJhbCBzdGF0aW9uLiBUbyB0aGUgcmlnaHQ6IFRocmVlIG91dCBvZiBzZXZlcmFsIHBvc3NpYmxlIGVuY29kaW5ncyBvZiBleHBsb3JhdGlvbiB0b3VycyBmb3IgdGhlIHN1YndheSBzeXN0ZW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiBpbnB1dCBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IHNjZW5hcmlvcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBzY2VuYXJpbyBjb25zaXN0cyBvZiB0d28gbGluZXMsIGVhY2ggY29udGFpbmluZyBhIHN0cmluZyBvZiB0aGUgY2hhcmFjdGVycyAmIzM5OzAmIzM5OyBhbmQgJiMzOTsxJiMzOTsgb2YgbGVuZ3RoIGF0IG1vc3QgMzAwMCwgYm90aCBkZXNjcmliaW5nIGEgY29ycmVjdCBleHBsb3JhdGlvbiB0b3VyIG9mIGEgc3Vid2F5IHRyZWUgc3lzdGVtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3Qgc2NlbmFyaW8sIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSB0ZXh0ICZsZHF1bztzYW1lJnJkcXVvOyBpZiB0aGUgdHdvIHN0cmluZ3MgbWF5IGVuY29kZSBleHBsb3JhdGlvbiB0b3VycyBvZiB0aGUgc2FtZSBzdWJ3YXkgdHJlZSBzeXN0ZW0sIG9yIHRoZSB0ZXh0ICZsZHF1bztkaWZmZXJlbnQmcmRxdW87IGlmIHRoZSB0d28gc3RyaW5ncyBjYW5ub3QgYmUgZXhwbG9yYXRpb24gdG91cnMgb2YgdGhlIHNhbWUgc3Vid2F5IHRyZWUgc3lzdGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==