시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 5203 3288 2413 63.400%

문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 \(\begin{pmatrix} 1 & \dots & i & \dots &n \\  \pi_1& \dots& \pi_i & \dots & \pi_n \end{pmatrix}\) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

예제 입력 1

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

예제 출력 1

3
7
W3sicHJvYmxlbV9pZCI6IjEwNDUxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjFjXHVjNWY0IFx1YzBhY1x1Yzc3NFx1ZDA3NCIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvcGVybXV0LnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMzRweDsgd2lkdGg6MjY0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+MVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YzgxNVx1YzIxOCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA4XHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjFjXHVjNWY0ICgzLCAyLCA3LCA4LCAxLCA0LCA1LCA2KVx1Yzc0NCBcdWJjMzBcdWM1ZjRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YmE3NCBcXChcXGJlZ2lue3BtYXRyaXh9IDEgJmFtcDsgMiAmYW1wOzMmYW1wOzQmYW1wOzUmYW1wOzYmYW1wOzcmYW1wOzggXFxcXCAmbmJzcDszJmFtcDsgMiZhbXA7NyZhbXA7OCZhbXA7MSZhbXA7NCZhbXA7NSZhbXA7NiBcXGVuZHtwbWF0cml4fVxcKSBcdWM2NDAgXHVhYzE5XHViMmU0LiBcdWI2MTBcdWIyOTQsIEZpZ3VyZSAxXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJjMjlcdWQ1YTUgXHVhZGY4XHViNzk4XHVkNTA0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMWNcdWM1ZjRcdWM3NDQgXHViYzMwXHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcXChcXGJlZ2lue3BtYXRyaXh9IDEgJmFtcDsgXFxkb3RzICZhbXA7IGkgJmFtcDsgXFxkb3RzICZhbXA7biBcXFxcICZuYnNwO1xccGlfMSZhbXA7IFxcZG90cyZhbXA7IFxccGlfaSAmYW1wOyBcXGRvdHMgJmFtcDsgXFxwaV9uIFxcZW5ke3BtYXRyaXh9XFwpIFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYzhcdWIyZTRcdWJhNzQsIGlcdWM1ZDBcdWMxMWMgJnBpOzxzdWI+aTxcL3N1Yj5cdWI4NWMgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1Yzc3NFx1YzViNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxXHVjNWQwIFx1YjA5OFx1YzY0MFx1Yzc4OFx1YjI5NCBcdWFjODMgXHVjYzk4XHViN2ZjLCBcdWMyMWNcdWM1ZjQgXHVhZGY4XHViNzk4XHVkNTA0ICgzLCAyLCA3LCA4LCAxLCA0LCA1LCA2KSBcdWM1ZDBcdWIyOTQgXHVjZDFkIDNcdWFjMWNcdWM3NTggXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc0NCAmcXVvdDtcdWMyMWNcdWM1ZjQgXHVjMGFjXHVjNzc0XHVkMDc0JnF1b3Q7IFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMjFjXHVjNWY0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgTiAoMiAmbGU7IE4gJmxlOyAxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMSBcdWM4MTVcdWMyMThcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjNWY0XHVjNWQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWMyMWNcdWM1ZjQgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA0NTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQZXJtdXRhdGlvbiBDeWNsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3Blcm11dC5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTM0cHg7IHdpZHRoOjI2NHB4XCIgXC8+VGhlcmUgYXJlIHNldmVyYWwgd2F5cyB0byByZXByZXNlbnQgYSBwZXJtdXRhdGlvbiBvZiB0aGUgbiBpbnRlZ2VycyBmcm9tIDEgdG8gbi4gRm9yIGV4YW1wbGUsIHdoZW4gdGhlIHBlcm11dGF0aW9uIG9mIDggaW50ZWdlcnMgaXMgKDMsMiw3LDgsMSw0LDUsNiksIG9uZSB3YXkgdG8gcmVwcmVzZW50IGl0IGFzIGFuIGFycmF5IGlzIFxcKFxcYmVnaW57cG1hdHJpeH0gMSAmYW1wOyAyICZhbXA7MyZhbXA7NCZhbXA7NSZhbXA7NiZhbXA7NyZhbXA7OCBcXFxcICZuYnNwOzMmYW1wOyAyJmFtcDs3JmFtcDs4JmFtcDsxJmFtcDs0JmFtcDs1JmFtcDs2IFxcZW5ke3BtYXRyaXh9XFwpLiBBbm90aGVyIHdheSB0byByZXByZXNlbnQgaXQgaW4gY3ljbGUtYXJyb3cgZm9ybSBpcyBzaG93biBpbiBGaWd1cmUgMS48XC9wPlxyXG5cclxuPHA+SWYgd2UgcmVwcmVzZW50IGEgcGVybXV0YXRpb24gYXMgYW4gYXJyYXkgXFwoXFxiZWdpbntwbWF0cml4fSAxICZhbXA7IFxcZG90cyAmYW1wOyBpICZhbXA7IFxcZG90cyAmYW1wO24gXFxcXCAmbmJzcDtcXHBpXzEmYW1wOyBcXGRvdHMmYW1wOyBcXHBpX2kgJmFtcDsgXFxkb3RzICZhbXA7IFxccGlfbiBcXGVuZHtwbWF0cml4fVxcKSB0aGVuIHRoZXJlIGlzIGEgZGlyZWN0ZWQgZWRnZSBmcm9tIGkgdG8gJnBpO2kgaW4gaXRzIGNvcnJlc3BvbmRpbmcgY3ljbGUtYXJyb3cgZm9ybSBmb3IgZWFjaCBpLjxcL3A+XHJcblxyXG48cD5BcyBzaG93biBpbiBGaWd1cmUgMSwgdGhlcmUgYXJlIDMgY3ljbGVzIHdoZW4gd2UgcmVwcmVzZW50IHBlcm11dGF0aW9uICgzLDIsNyw4LDEsNCw1LDYpIGluIGN5Y2xlLWFycm93IGZvcm0uIFdlIGNhbGwgdGhlc2UgY3ljbGVzICZsc3F1bztwZXJtdXRhdGlvbiBjeWNsZXMuJnJzcXVvOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCBjb3VudHMgdGhlIG51bWJlciBvZiBwZXJtdWF0aW9uIGN5Y2xlcyBpbiBhIGdpdmVuIHBlcm11dGF0aW9uIG9mIG4gaW50ZWdlcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbiAoMiAmbGU7IG4gJmxlOyAxLDAwMCkuIEluIHRoZSBmb2xsb3dpbmcgbGluZSB0aGVyZSBpcyBhIHBlcm11dGF0aW9uIG9mIG4gaW50ZWdlcnMgZnJvbSAxIHRvIG4uIEVhY2ggaW50ZWdlciBpbiBhIHBlcm11dGF0aW9uIGlzIHNlcGFyYXRlZCBieSBhIGJsYW5rLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHBlcm11dGF0aW9uIGN5Y2xlcyBpbiB0aGUgZ2l2ZW4gcGVybXV0YXRpb24uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2014 F번