시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 6225 3924 2866 63.774%

문제

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+MVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YzgxNVx1YzIxOCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgOFx1YWMxY1x1Yzc1OCBcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxY1x1YzVmNCAoMywgMiwgNywgOCwgMSwgNCwgNSwgNilcdWM3NDQgXHViYzMwXHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWJhNzQgXFwoXFxiZWdpbntwbWF0cml4fSAxICZhbXA7IDIgJmFtcDszJmFtcDs0JmFtcDs1JmFtcDs2JmFtcDs3JmFtcDs4IFxcXFwgJm5ic3A7MyZhbXA7IDImYW1wOzcmYW1wOzgmYW1wOzEmYW1wOzQmYW1wOzUmYW1wOzYgXFxlbmR7cG1hdHJpeH1cXCkgXHVjNjQwIFx1YWMxOVx1YjJlNC4gXHViNjEwXHViMjk0LCBGaWd1cmUgMVx1YWNmYyBcdWFjMTlcdWM3NzQgXHViYzI5XHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjFjXHVjNWY0XHVjNzQ0IFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXFwoXFxiZWdpbntwbWF0cml4fSAxICZhbXA7IFxcZG90cyAmYW1wOyBpICZhbXA7IFxcZG90cyAmYW1wO24gXFxcXCAmbmJzcDtcXHBpXzEmYW1wOyBcXGRvdHMmYW1wOyBcXHBpX2kgJmFtcDsgXFxkb3RzICZhbXA7IFxccGlfbiBcXGVuZHtwbWF0cml4fVxcKSBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGM4XHViMmU0XHViYTc0LCBpXHVjNWQwXHVjMTFjICZwaTs8c3ViPmk8XC9zdWI+XHViODVjIFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWM3NzRcdWM1YjQgXHVhZGY4XHViNzk4XHVkNTA0XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMVx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgXHVhYzgzIFx1Y2M5OFx1YjdmYywgXHVjMjFjXHVjNWY0IFx1YWRmOFx1Yjc5OFx1ZDUwNCAoMywgMiwgNywgOCwgMSwgNCwgNSwgNikgXHVjNWQwXHViMjk0IFx1Y2QxZCAzXHVhYzFjXHVjNzU4IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NDQgJnF1b3Q7XHVjMjFjXHVjNWY0IFx1YzBhY1x1Yzc3NFx1ZDA3NCZxdW90OyBcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjFjXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzIxY1x1YzVmNCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwIE4gKDIgJmxlOyBOICZsZTsgMSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWFjMDEgXHVjODE1XHVjMjE4XHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxY1x1YzVmNFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVjMjFjXHVjNWY0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNDUxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGVybXV0YXRpb24gQ3ljbGVzIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9wZXJtdXQucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjEzNHB4OyB3aWR0aDoyNjRweFwiIFwvPlRoZXJlIGFyZSBzZXZlcmFsIHdheXMgdG8gcmVwcmVzZW50IGEgcGVybXV0YXRpb24gb2YgdGhlIG4gaW50ZWdlcnMgZnJvbSAxIHRvIG4uIEZvciBleGFtcGxlLCB3aGVuIHRoZSBwZXJtdXRhdGlvbiBvZiA4IGludGVnZXJzIGlzICgzLDIsNyw4LDEsNCw1LDYpLCBvbmUgd2F5IHRvIHJlcHJlc2VudCBpdCBhcyBhbiBhcnJheSBpcyBcXChcXGJlZ2lue3BtYXRyaXh9IDEgJmFtcDsgMiAmYW1wOzMmYW1wOzQmYW1wOzUmYW1wOzYmYW1wOzcmYW1wOzggXFxcXCAmbmJzcDszJmFtcDsgMiZhbXA7NyZhbXA7OCZhbXA7MSZhbXA7NCZhbXA7NSZhbXA7NiBcXGVuZHtwbWF0cml4fVxcKS4gQW5vdGhlciB3YXkgdG8gcmVwcmVzZW50IGl0IGluIGN5Y2xlLWFycm93IGZvcm0gaXMgc2hvd24gaW4gRmlndXJlIDEuPFwvcD5cclxuXHJcbjxwPklmIHdlIHJlcHJlc2VudCBhIHBlcm11dGF0aW9uIGFzIGFuIGFycmF5IFxcKFxcYmVnaW57cG1hdHJpeH0gMSAmYW1wOyBcXGRvdHMgJmFtcDsgaSAmYW1wOyBcXGRvdHMgJmFtcDtuIFxcXFwgJm5ic3A7XFxwaV8xJmFtcDsgXFxkb3RzJmFtcDsgXFxwaV9pICZhbXA7IFxcZG90cyAmYW1wOyBcXHBpX24gXFxlbmR7cG1hdHJpeH1cXCkgdGhlbiB0aGVyZSBpcyBhIGRpcmVjdGVkIGVkZ2UgZnJvbSBpIHRvICZwaTtpIGluIGl0cyBjb3JyZXNwb25kaW5nIGN5Y2xlLWFycm93IGZvcm0gZm9yIGVhY2ggaS48XC9wPlxyXG5cclxuPHA+QXMgc2hvd24gaW4gRmlndXJlIDEsIHRoZXJlIGFyZSAzIGN5Y2xlcyB3aGVuIHdlIHJlcHJlc2VudCBwZXJtdXRhdGlvbiAoMywyLDcsOCwxLDQsNSw2KSBpbiBjeWNsZS1hcnJvdyBmb3JtLiBXZSBjYWxsIHRoZXNlIGN5Y2xlcyAmbHNxdW87cGVybXV0YXRpb24gY3ljbGVzLiZyc3F1bzs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2ggY291bnRzIHRoZSBudW1iZXIgb2YgcGVybXVhdGlvbiBjeWNsZXMgaW4gYSBnaXZlbiBwZXJtdXRhdGlvbiBvZiBuIGludGVnZXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIG4gKDIgJmxlOyBuICZsZTsgMSwwMDApLiBJbiB0aGUgZm9sbG93aW5nIGxpbmUgdGhlcmUgaXMgYSBwZXJtdXRhdGlvbiBvZiBuIGludGVnZXJzIGZyb20gMSB0byBuLiBFYWNoIGludGVnZXIgaW4gYSBwZXJtdXRhdGlvbiBpcyBzZXBhcmF0ZWQgYnkgYSBibGFuay48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBwZXJtdXRhdGlvbiBjeWNsZXMgaW4gdGhlIGdpdmVuIHBlcm11dGF0aW9uLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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