시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 8087 1947 1235 23.869%

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

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

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

예제 입력 1

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

예제 출력 1

3
0

힌트

W3sicHJvYmxlbV9pZCI6Ijk0NjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNDAgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWJjODggXHVhYzAwXHVjNzQ0XHVkNTU5XHVhZTMwXHVjNWQwICYjMzk7XHViYjM4XHVjODFjIFx1ZDU3NFx1YWNiMCYjMzk7IFx1YWMxNVx1Yzc1OFx1Yjk3YyBcdWMyZTBcdWNjYWRcdWQ1NWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwJm5ic3A7XHVkMTQwIFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1Yjk3YyBcdWMyMThcdWQ1ODlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjggXHVkMzAwXHVjNmQwIFx1YzIxOFx1YzVkMFx1YjI5NCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNWM2XHViMmU0LiBcdWMyZWNcdWM5YzBcdWM1YjQgXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVkMzAwXHVjNzU4IFx1ZDMwMFx1YzZkMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM2NDAmbmJzcDtcdWFjMTlcdWM3NzQmbmJzcDtcdWQ1NWMgXHVkMzAwXHViOWNjIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjggXHVkMzAwXHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQsJm5ic3A7XHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWI5N2MgXHVkNTY4XHVhZWQ4XHVkNTU4XHVhY2UwIFx1YzJmNlx1Yzc0MCZuYnNwO1x1ZDU1OVx1YzBkZFx1Yzc0NCZuYnNwO1x1YzEyMFx1ZDBkZFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIChcdWIyZTgsIFx1YjJlOCBcdWQ1NWNcdWJhODVcdWI5Y2MgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuKSZuYnNwO1x1ZDYzY1x1Yzc5MCBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWFjODNcdWIzYzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQoczxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCAuLi4sIHM8c3ViPnI8XC9zdWI+KVx1Yzc3NFx1Yjc3YyBcdWQ1NjAgXHViNTRjLCZuYnNwO3I9MVx1Yzc3NFx1YWNlMCBzPHN1Yj4xPFwvc3ViPlx1Yzc3NCBzPHN1Yj4xPFwvc3ViPlx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMDk4LCBzPHN1Yj4xPFwvc3ViPlx1Yzc3NCBzPHN1Yj4yPFwvc3ViPlx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjZTAsIHM8c3ViPjI8XC9zdWI+XHVhYzAwIHM8c3ViPjM8XC9zdWI+XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YWNlMCwuLi4sIHM8c3ViPnItMTxcL3N1Yj5cdWM3NzQgczxzdWI+cjxcL3N1Yj5cdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBzPHN1Yj5yPFwvc3ViPlx1Yzc3NCBzPHN1Yj4xPFwvc3ViPlx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViOWNjIFx1ZDU1YyBcdWQzMDBcdWM3NzQgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDU1YyBcdWJjMThcdWM1ZDAgN1x1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IDFcdWJjODhcdWJkODBcdWQxMzAgN1x1YmM4OFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHViNTRjLCBcdWMxMjBcdWQwZGRcdWM3NTggXHVhY2IwXHVhY2ZjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozMCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0aD4zPFwvdGg+XHJcblx0XHRcdDx0aD40PFwvdGg+XHJcblx0XHRcdDx0aD41PFwvdGg+XHJcblx0XHRcdDx0aD42PFwvdGg+XHJcblx0XHRcdDx0aD43PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHRcdDx0ZD42PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhY2IwXHVhY2ZjXHViOTdjIFx1ZDFiNVx1ZDU3NCAoMylcdWFjZmMgKDQsIDcsIDYpXHVjNzc0IFx1ZDMwMFx1Yzc0NCBcdWM3NzRcdWI4ZjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gMSwgMiwgNVx1YjI5NCBcdWM1YjRcdWIyOTAgXHVkMzAwXHVjNWQwXHViM2M0IFx1YzE4ZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWMxMjBcdWQwZGRcdWM3NTggXHVhY2IwXHVhY2ZjXHViOTdjIFx1YmNmNFx1YWNlMCBcdWM1YjRcdWIyOTAgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4IFx1ZDMwMFx1YzVkMFx1YjNjNCBcdWMxOGRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjODE1XHVjMjE4Jm5ic3A7biAoMiAmbGU7IG4mbmJzcDsmbGU7IDEwMCwwMDApXHVjNzNjXHViODVjJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7XHVjMTIwXHVkMGRkXHViNDFjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOyhcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDgwXHVjNWVjXHViNDFjXHViMmU0Lik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjggXHVkMzAwXHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk0NjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUZXJtIFByb2plY3QiLCJkZXNjcmlwdGlvbiI6IjxwPlN0dWRlbnRzIHdobyBlbnJvbGxlZCBpbiB0aGUgJmxzcXVvO1Byb2JsZW0gU29sdmluZyZyc3F1bzsgY291cnNlIGluIHRoaXMgZmFsbCBzZW1lc3RlciBoYXZlIHRvIGNhcnJ5IG91dCBhIHRlcm0gcHJvamVjdC4gVGhlcmUgaXMgbm8gbGltaXQgdG8gdGhlIG51bWJlciBvZiBwcm9qZWN0IHRlYW0gbWVtYmVycy4gRXZlbiBvbmUgdGVhbSBpcyBhbGxvd2VkIHN1Y2ggdGhhdCBhbGwgc3R1ZGVudHMgYXJlIG1lbWJlcnMgb2YgdGhlIHNhbWUgdGVhbS4gSW4gb3JkZXIgdG8gZm9ybSBwcm9qZWN0IHRlYW1zLCBldmVyeSBzdHVkZW50IHNob3VsZCBzZWxlY3QgYSBmcmllbmQgd2l0aCB3aG9tIGhlIG9yIHNoZSB3YW50cyB0byB3b3JrLiBBIHN0dWRlbnQgd2hvIHdhbnRzIHRvIHdvcmsgYWxvbmUgY2FuIHNlbGVjdCBoaW1zZWxmIG9yIGhlcnNlbGYuIEEgc3R1ZGVudCBsaXN0IChzPHN1Yj4xPFwvc3ViPiwgczxzdWI+MjxcL3N1Yj4sIC4uLiwgczxzdWI+cjxcL3N1Yj4pIGNhbiBiZSBhIHRlYW0gaWYgZWl0aGVyIHI9MSBhbmQgczxzdWI+MTxcL3N1Yj4gc2VsZWN0cyBzPHN1Yj4xPFwvc3ViPiBvciBzPHN1Yj4xPFwvc3ViPiBzZWxlY3RzIHM8c3ViPjI8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiBzZWxlY3RzIHM8c3ViPjM8XC9zdWI+LCAmaGVsbGlwOyAsIHM8c3ViPnItMTxcL3N1Yj4gc2VsZWN0cyBzPHN1Yj5yPFwvc3ViPiwgYW5kIHM8c3ViPnI8XC9zdWI+Jm5ic3A7c2VsZWN0cyBzPHN1Yj4xPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCZyc3F1bztzIGFzc3VtZSB0aGF0IHRoZXJlIGFyZSA3IHN0dWRlbnRzIGluIHRoZSBjbGFzcy4gVGhlIHN0dWRlbnRzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gNy4gVGhlIGZvbGxvd2luZyBpcyB0aGUgcmVzdWx0IG9mIHRoZSBzZWxlY3Rpb24uPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozMCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0aD4zPFwvdGg+XHJcblx0XHRcdDx0aD40PFwvdGg+XHJcblx0XHRcdDx0aD41PFwvdGg+XHJcblx0XHRcdDx0aD42PFwvdGg+XHJcblx0XHRcdDx0aD43PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHRcdDx0ZD42PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5Gcm9tIHRoZSBhYm92ZSByZXN1bHQsIHdlIGNhbiBzZWUgdGhhdCB0d28gdGVhbXMgKDMpIGFuZCAoNCwgNywgNikgYXJlIGZvcm1lZC4gU3R1ZGVudHMgMSwgMiwgYW5kIDUgZG9uJnJzcXVvO3QgYmVsb25nIHRvIGFueSB0ZWFtLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgcmVzdWx0IG9mIHRoZSBzZWxlY3Rpb24sIHdyaXRlIGEgcHJvZ3JhbSB0byBjb21wdXRlIHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMgd2hvIGRvbiZyc3F1bzt0IGJlbG9uZyB0byBhIHByb2plY3QgdGVhbS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBuICgyICZsZTsgbiAmbGU7IDEwMCAwMDApLCB3aGVyZSBuIGlzIHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMgaW4gdGhlIGNsYXNzLiBBbGwgc3R1ZGVudHMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBUaGUgbmV4dCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIG4gaW50ZWdlcnMgczxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCAuLi4sIHM8c3ViPm48XC9zdWI+LCB3aGVyZSBzPHN1Yj5pPFwvc3ViPiZuYnNwO2lzIHRoZSBzdHVkZW50IHdobyB3YXMgYSBzdHVkZW50IFx1MDc0NSBzZWxlY3RlZCBieS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBzdHVkZW50cyB3aG8gZG9uJnJzcXVvO3QgYmVsb25nIHRvIGEgcHJvamVjdCB0ZWFtLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

  • 데이터를 추가한 사람: cubelover
  • 문제를 번역한 사람: plzrun