시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 69 19 15 34.091%

문제

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+XHVkMmI4XHViOWFjXHViOTdjIFx1ZDBkMFx1YzBjOVx1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVhY2JkXHViODVjXHViNGU0XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVkMGQwXHVjMGM5XHVkNTVjIFx1YWM4M1x1Yzc3OFx1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMzcwXHVjNzc0XHVkMTMwXHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEmbGU7VCZsZTsxMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgMiZ0aW1lcztUXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVkMGQwXHVjMGM5XHVkNTVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMywwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBUXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWM3NDQgXHVkNTU4XHViMjk0XHViMzcwLCBcdWI5Y2NcdWM1N2QgXHVhYzE5XHVjNzQwIFx1ZDJiOFx1YjlhY1x1Yjc3Y1x1YmE3NCAxXHVjNzQ0LCBcdWIyZTRcdWI5NzggXHVkMmI4XHViOWFjXHViNzdjXHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzNzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdWJ3YXkgdHJlZSBzeXN0ZW1zIiwiZGVzY3JpcHRpb24iOiI8cD5Tb21lIG1ham9yIGNpdGllcyBoYXZlIHN1YndheSBzeXN0ZW1zIGluIHRoZSBmb3JtIG9mIGEgdHJlZSwgaS5lLiBiZXR3ZWVuIGFueSBwYWlyIG9mIHN0YXRpb25zLCB0aGVyZSBpcyBvbmUgYW5kIG9ubHkgb25lIHdheSBvZiBnb2luZyBieSBzdWJ3YXkuIE1vcmVvdmVyLCBtb3N0IG9mIHRoZXNlIGNpdGllcyBoYXZlIGEgdW5pcXVlIGNlbnRyYWwgc3RhdGlvbi4gSW1hZ2luZSB5b3UgYXJlIGEgdG91cmlzdCBpbiBvbmUgb2YgdGhlc2UgY2l0aWVzIGFuZCB5b3Ugd2FudCB0byBleHBsb3JlIGFsbCBvZiB0aGUgc3Vid2F5IHN5c3RlbS4gWW91IHN0YXJ0IGF0IHRoZSBjZW50cmFsIHN0YXRpb24gYW5kIHBpY2sgYSBzdWJ3YXkgbGluZSBhdCByYW5kb20gYW5kIGp1bXAgYWJvYXJkIHRoZSBzdWJ3YXkgY2FyLiBFdmVyeSB0aW1lIHlvdSBhcnJpdmUgYXQgYSBzdGF0aW9uLCB5b3UgcGljayBvbmUgb2YgdGhlIHN1YndheSBsaW5lcyB5b3UgaGF2ZSBub3QgeWV0IHRyYXZlbGxlZCBvbi4gSWYgdGhlcmUgaXMgbm9uZSBsZWZ0IHRvIGV4cGxvcmUgYXQgeW91ciBjdXJyZW50IHN0YXRpb24sIHlvdSB0YWtlIHRoZSBzdWJ3YXkgbGluZSBiYWNrIG9uIHdoaWNoIHlvdSBmaXJzdCBjYW1lIHRvIHRoZSBzdGF0aW9uLCB1bnRpbCB5b3UgZXZlbnR1YWxseSBoYXZlIHRyYXZlbGxlZCBhbG9uZyBhbGwgb2YgdGhlIGxpbmVzIHR3aWNlLCBvbmNlIGZvciBlYWNoIGRpcmVjdGlvbi4gQXQgdGhhdCBwb2ludCB5b3UgYXJlIGJhY2sgYXQgdGhlIGNlbnRyYWwgc3RhdGlvbi4gQWZ0ZXJ3YXJkcywgYWxsIHlvdSByZW1lbWJlciBvZiB0aGUgb3JkZXIgb2YgeW91ciBleHBsb3JhdGlvbiBpcyB3aGV0aGVyIHlvdSB3ZW50IGZ1cnRoZXIgYXdheSBmcm9tIHRoZSBjZW50cmFsIHN0YXRpb24gb3IgYmFjayB0b3dhcmRzIGl0IGF0IGFueSBnaXZlbiB0aW1lLCBpLmUuIHlvdSBjb3VsZCBlbmNvZGUgeW91ciB0b3VyIGFzIGEgYmluYXJ5IHN0cmluZywgd2hlcmUgMCBlbmNvZGVzIHRha2luZyBhIHN1YndheSBsaW5lIGdldHRpbmcgeW91IG9uZSBzdGF0aW9uIGZ1cnRoZXIgYXdheSBmcm9tIHRoZSBjZW50cmFsIHN0YXRpb24sIGFuZCAxIGVuY29kZXMgZ2V0dGluZyB5b3Ugb25lIHN0YXRpb24gY2xvc2VyIHRvIHRoZSBjZW50cmFsIHN0YXRpb24uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3MucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTc5cHg7IHdpZHRoOjU4OXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxLiBUbyB0aGUgbGVmdDogQSBzdWJ3YXkgdHJlZSBzeXN0ZW0uIFRoZSBsYXJnZXIgZG90IGlzIHRoZSBjZW50cmFsIHN0YXRpb24uIFRvIHRoZSByaWdodDogVGhyZWUgb3V0IG9mIHNldmVyYWwgcG9zc2libGUgZW5jb2RpbmdzIG9mIGV4cGxvcmF0aW9uIHRvdXJzIGZvciB0aGUgc3Vid2F5IHN5c3RlbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGlzIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbiwgdGVsbGluZyB0aGUgbnVtYmVyIG9mIHRlc3Qgc2NlbmFyaW9zIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IHNjZW5hcmlvIGNvbnNpc3RzIG9mIHR3byBsaW5lcywgZWFjaCBjb250YWluaW5nIGEgc3RyaW5nIG9mIHRoZSBjaGFyYWN0ZXJzICYjMzk7MCYjMzk7IGFuZCAmIzM5OzEmIzM5OyBvZiBsZW5ndGggYXQgbW9zdCAzMDAwLCBib3RoIGRlc2NyaWJpbmcgYSBjb3JyZWN0IGV4cGxvcmF0aW9uIHRvdXIgb2YgYSBzdWJ3YXkgdHJlZSBzeXN0ZW0uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBzY2VuYXJpbywgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHRleHQgJmxkcXVvO3NhbWUmcmRxdW87IGlmIHRoZSB0d28gc3RyaW5ncyBtYXkgZW5jb2RlIGV4cGxvcmF0aW9uIHRvdXJzIG9mIHRoZSBzYW1lIHN1YndheSB0cmVlIHN5c3RlbSwgb3IgdGhlIHRleHQgJmxkcXVvO2RpZmZlcmVudCZyZHF1bzsgaWYgdGhlIHR3byBzdHJpbmdzIGNhbm5vdCBiZSBleHBsb3JhdGlvbiB0b3VycyBvZiB0aGUgc2FtZSBzdWJ3YXkgdHJlZSBzeXN0ZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d