시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 1142 350 254 34.511%

문제

그래프 G는 정점의 집합 V와 간선의 집합 E로 이루어져 있고, G = (V, E)로 나타낸다. 대부분의 경우에 V와 E는 명시되어 있다. 일부 그래프의 경우에는 집합이 명시되어 있지 않다. 예를 들어, 순열 그래프는 간선의 집합이 명시되어 있지 않다.

{1, 2, 3, 4, 5}로 이루어진 두 순열 (2, 5, 4, 1, 3)과 (1, 5, 3, 2, 4)가 있다. 평행선을 그리고, 그 위에 순열에 적힌 숫자 순서대로 정점을 그린다. 그 다음 같은 숫자끼리 선분을 연결한다. 아래 그림과 같이 교차하는 선분의 쌍은 총 여섯 개라는 것을 알 수 있다.

교차하는 쌍은 순열 그래프의 간선이 된다. 순열 그래프의 정점은 숫자가 되고, 간선은 교차하는 쌍이 된다. 위의 예를 이용해 순열 그래프를 만들면 V = {1, 2, 3, 4, 5}, E = {(1,2), (1,4), (1,5), (2,3), (2,5), (3,4)}. 위의 두 순열을 이용해 순열 그래프를 그리면 아래 그림과 같이 된다.

{1, 2, ..., n}으로 이루어진 두 순열이 주어졌을 때, 두 순열을 이용해 만든 순열 그래프의 간선의 개수를 구하는 프로그램을 작성하시오. 예를 들어, (2, 5, 4, 1, 3)과 (1, 5, 3, 2, 4)로 만든 순열 그래프의 간선의 개수는 6개이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n이 주어진다. 둘째 줄과 셋째 줄에는 두 순열이 주어진다. 순열은 {1, 2, ..., n}으로 이루어져 있고, 공백으로 구분되어져 있다. (1 ≤ n ≤ 100,000)

출력

각 테스트 케이스 마다, 입력으로 주어진 두 순열로 만든 순열 그래프의 간선의 개수를 출력한다.

예제 입력 1

3
5
2 5 4 1 3
1 5 3 2 4
7
5 6 7 1 2 3 4
5 6 7 1 2 3 4
7
1 5 3 4 2 7 6
7 1 5 3 4 2 6

예제 출력 1

6
0
5

힌트

W3sicHJvYmxlbV9pZCI6Ijk0NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWM1ZjQgXHVhZGY4XHViNzk4XHVkNTA0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFkZjhcdWI3OThcdWQ1MDQgR1x1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjOWQxXHVkNTY5IFZcdWM2NDAgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzlkMVx1ZDU2OSBFXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIEcgPSAoViwgRSlcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFZcdWM2NDAgRVx1YjI5NCBcdWJhODVcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM3N2NcdWJkODAgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHViYTg1XHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzIxY1x1YzVmNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc3NCBcdWJhODVcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+ezEsIDIsIDMsIDQsIDV9XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWI0NTAgXHVjMjFjXHVjNWY0ICgyLCA1LCA0LCAxLCAzKVx1YWNmYyAoMSwgNSwgMywgMiwgNClcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWQzYzlcdWQ1ODlcdWMxMjBcdWM3NDQgXHVhZGY4XHViOWFjXHVhY2UwLCBcdWFkZjggXHVjNzA0XHVjNWQwIFx1YzIxY1x1YzVmNFx1YzVkMCBcdWM4MDFcdWQ3OGMgXHVjMjJiXHVjNzkwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4MTVcdWM4MTBcdWM3NDQgXHVhZGY4XHViOWIwXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWIwN2NcdWI5YWMgXHVjMTIwXHViZDg0XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWMzMGRcdWM3NDAgXHVjZDFkIFx1YzVlY1x1YzEyZiBcdWFjMWNcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Blcm0xLnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVjMzBkXHVjNzQwIFx1YzIxY1x1YzVmNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjMjFjXHVjNWY0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NDAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjQxOFx1YWNlMCwgXHVhYzA0XHVjMTIwXHVjNzQwIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWMzMGRcdWM3NzQgXHViNDFjXHViMmU0LiBcdWM3MDRcdWM3NTggXHVjNjA4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWMyMWNcdWM1ZjQgXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1YjljY1x1YjRlNFx1YmE3NCBWID0gezEsIDIsIDMsIDQsIDV9LCBFID0geygxLDIpLCAoMSw0KSwgKDEsNSksICgyLDMpLCAoMiw1KSwgKDMsNCl9LiBcdWM3MDRcdWM3NTggXHViNDUwIFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjMjFjXHVjNWY0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWFkZjhcdWI5YWNcdWJhNzQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Blcm0yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1MHB4OyB3aWR0aDoyMzJweFwiIFwvPjxcL3A+XHJcblxyXG48cD57MSwgMiwgLi4uLCBufVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViNDUwIFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWI5Y2NcdWI0ZTAgXHVjMjFjXHVjNWY0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMiwgNSwgNCwgMSwgMylcdWFjZmMgKDEsIDUsIDMsIDIsIDQpXHViODVjIFx1YjljY1x1YjRlMCBcdWMyMWNcdWM1ZjQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgNlx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWFjZmMgXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjMjFjXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjFjXHVjNWY0XHVjNzQwIHsxLCAyLCAuLi4sIG59XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWI0NTAgXHVjMjFjXHVjNWY0XHViODVjIFx1YjljY1x1YjRlMCBcdWMyMWNcdWM1ZjQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk0NjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQZXJtdXRhdGlvbiBHcmFwaHMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgZ3JhcGggRyBpcyBkZWZpbmVkIGFzIGEgdHVwbGUgb2YgdGhlIHNldCBvZiB2ZXJ0aWNlcyBWIGFuZCB0aGUgc2V0IG9mIGVkZ2VzIEUsIGkuZS4gRyA9IChWLCBFKS4gVGhlIHR3byBzZXRzLCBWIGFuZCBFLCBhcmUgdXN1YWxseSBnaXZlbiBleHBsaWNpdGx5LiBGb3Igc29tZSBncmFwaHMsIGhvd2V2ZXIsIHRoZXNlIHNldHMgYXJlIGdpdmVuIGltcGxpY2l0bHkuIEEgcGVybXVhdGlvbiBncmFwaCBpcyBzdWNoIGEgZ3JhcGgsIHdoZXJlIHRoZSBzZXQgb2YgZWRnZXMgaXMgZ2l2ZW4gaW1wbGljaXRseS4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuRm9yIGluc3RhbmNlLCBjb25zaWRlciB0d28gcGVybXV0YXRpb25zICgyLCA1LCA0LCAxLCAzKSBhbmQgKDEsIDUsIDMsIDIsIDQpIG9mIHRoZSBudW1iZXJzIHsxLCAyLCAzLCA0LCA1fS4gSWYgd2UgZHJhdyBsaW5lIHNlZ21lbnRzIGNvbm5lY3RpbmcgdGhlIGNvcnJlc3BvbmRpbmcgbnVtYmVycyBiZXR3ZWVuIHR3byBwYXJhbGxlbCBsaW5lcywgY29udGFpbmluZyB0aGUgdmVydGljZXMgaW4gdGhlIHR3byBwZXJtdXRhdGlvbiBvcmRlcnMsIHdlIGNhbiBmaW5kIHNpeCBpbnRlcnNlY3RpbmcgcGFpcnMgb2YgbGluZSBzZWdtZW50cyBhcyBzaG93biBpbiBGaWd1cmUgMS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wZXJtMS5wbmdcIiBzdHlsZT1cIm9wYWNpdHk6MC45XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBTaXggaW50ZXJzZWN0aW5nIHBhaXJzIG9mIGxpbmUgc2VnbWVudHMgZ2l2ZW4gdHdvIHBlcm11dGF0aW9ucyZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaW50ZXJzZWN0aW5nIHBhaXJzIGRlZmluZSBhIHBlcm11dGF0aW9uIGdyYXBoLiBJdHMgdmVydGljZXMgYXJlIHRoZSBudW1iZXJzIGFuZCBpdHMgZWRnZXMgYXJlIHRoZSBpbnRlcnNlY3RpbmcgcGFpcnMuIEluIHRoaXMgZXhhbXBsZSwgViA9IHsxLCAyLCAzLCA0LCA1fSBhbmQgRSA9IHsoMSwgMiksICgxLCA0KSwgKDEsIDUpLCAoMiwgMyksICgyLCA1KSwgKDMsIDQpfS4gVGhpcyBraW5kIG9mIGdyYXBocyBpcyBjYWxsZWQgYSBwZXJtdXRhdGlvbiBncmFwaC4gVGhlIHR3byBwZXJtdXRhdGlvbnMgYWJvdmUgZGVmaW5lIHRoZSBwZXJtdXRhdGlvbiBncmFwaCBhcyBzaG93biBpbiBGaWd1cmUgMi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wZXJtMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTBweDsgd2lkdGg6MjMycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDI6IFRoZSBwZXJtdXRhdGlvbiBncmFwaCBkZWZpbmVkIGJ5IHR3byBwZXJtdXRhdGlvbnMgKDIsIDUsIDQsIDEsIDMpIGFuZCAoMSwgNSwgMywgMiwgNCk8XC9wPlxyXG5cclxuPHA+VGhlIHByb2JsZW0gaXMgdG8gZmluZCB0aGUgbnVtYmVyIG9mIGVkZ2VzIG9mIHRoZSBwZXJtdXRhdGlvbiBncmFwaCBnaXZlbiB0d28gcGVybXV0YXRpb25zIG9mIHRoZSBzYW1lIHNldCBvZiBudW1iZXJzIHsxLCAyLCAmaGVsbGlwOywgbn0gZm9yIHNvbWUgbi4gRm9yIGluc3RhbmNlLCBpZiB0aGUgdHdvIHBlcm11dGF0aW9ucyAoMiwgNSwgNCwgMSwgMykgYW5kICgxLCA1LCAzLCAyLCA0KSBhcmUgZ2l2ZW4gYXMgaW5wdXQsIHlvdXIgcHJvZ3JhbSBzaG91bGQgcHJpbnQgNi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRnJvbSB0aGUgc2Vjb25kIGxpbmUsIGVhY2ggdGVzdCBjYXNlIGlzIGdpdmVuLiBBIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0aHJlZSBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgbiwgdGhlIHVwcGVyIGJvdW5kIG9mIHRoZSBlbGVtZW50cyBvZiB0aGUgc2V0IHsxLCAyLCAmaGVsbGlwOywgbn0gZm9yIHdoaWNoIHRoZSBwZXJtdXRhdGlvbnMgYXJlIHRvIGJlIGRlZmluZWQuIFRoZSBzZWNvbmQgYW5kIHRoZSB0aGlyZCBsaW5lcyBvZiB0aGUgdGVzdCBjYXNlIGNvbnRhaW4gdHdvIHBlcm11dGF0aW9ucy4gVGhlIHBlcm11dGF0aW9ucyBhcmUgZ2l2ZW4gYXMgYSBzZXF1ZW5jZSBvZiBuYXR1cmFsIG51bWJlcnMgaW4gezEsIDIsICZoZWxsaXA7LCBufSBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlLiBUaGUgbGFyZ2VzdCBwb3NzaWJsZSBudW1iZXIgbiBvZiBhIHBlcm11dGF0aW9uIGlzIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxMDAsMDAwICgxICZsZTsgbiAmbGU7IDEwMCwwMDApLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIGVkZ2VzIGZvciB0aGUgcGVybXV0YXRpb24gZ3JhcGggY29ycmVzcG9uZGluZyB0byBlYWNoIHRlc3QgY2FzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2013 I번