시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB40171147.826%

문제

총 $N$명의 병사들을 두 팀으로 나누어 진행된 부대 축구 대회가 끝난 뒤, 최고의 플레이어를 뽑기 위한 MVP 투표를 진행하려고 한다.

그러나 아무런 조건 없이 투표하게 되면 모두가 본인의 팀에게 투표할 것이 뻔하므로, 모든 병사들은 상대 팀의 병사에게만 투표할 것을 약속했다. 이에 $1$번 병사부터 $N$번 병사까지, 경기에 참여한 모든 $N$명의 병사들은 상대 팀 병사를 한 명씩 지목하여 투표했다.

하지만 투표가 끝난 뒤 이 약속을 어긴 거짓말쟁이가 한 명 있었다는 제보가 들어왔다. 그러나 각 병사들이 어떤 팀인지에 대한 정보가 분실되어, 거짓말쟁이를 찾을 증거는 각 병사가 누구를 투표했는지 정리된 자료와, 두 팀 중 적어도 하나의 팀의 인원수가 최소 $M$명 이상이었다는 증언뿐이다.

주어진 증거들을 토대로 거짓말쟁이 용의자들을 모두 추려내 보자.

입력

첫 번째 줄에 투표에 참여한 병사의 수 $N$과, 두 팀 중 적어도 하나의 팀의 최소 인원수 $M$이 공백으로 구분되어 주어진다. $(3\leq N\leq 200\,000;$ $1\leq M<N)$

두 번째 줄에 $i$번 병사가 MVP로 투표한 병사의 번호를 나타내는 정수 $v_i$가 공백으로 구분되어 주어진다. $(1\leq v_i\leq N;$ $v_i\neq i)$

출력

첫 번째 줄에 거짓말쟁이가 될 수 있는 용의자의 수를 출력한다.

두 번째 줄에 용의자들의 번호를 공백으로 구분하여 오름차순으로 출력한다.

만약 어떤 병사가 거짓말쟁이어도 입력으로 주어진 상황이 만들어질 수 없다면, 첫 번째 줄에 $-1$을 출력한다.

예제 입력 1

8 5
7 7 7 6 4 8 4 5

예제 출력 1

1
7

각 팀을 $A$팀과 $B$팀이라고 할 때, $7$번 병사를 거짓말쟁이라고 가정하면 각 팀의 인원은 다음과 같다.

$A$팀 : $\{1, 2, 3, 5, 6\}$

$B$팀 : $\{4, 7, 8\}$

이 경우, 거짓말쟁이인 $7$번 병사를 제외하면 모두 서로 다른 팀에 투표하였으며, 팀 $A$의 인원수가 $5$명 이상이므로 조건에 부합한다.

예제 입력 2

8 6
7 7 7 6 4 8 4 5

예제 출력 2

-1

어떤 병사가 거짓말쟁이라 하더라도 적어도 하나의 팀의 인원수가 $6$명 이상인 경우는 존재하지 않는다.

예제 입력 3

4 2
2 4 1 3

예제 출력 3

-1

거짓말쟁이가 아예 없거나 거짓말쟁이가 동시에 두 명 또는 네 명 존재해야만 발생할 수 있는 경우이며, 이는 거짓말쟁이가 한 명이라는 조건에 어긋난다.

출처

Contest > 보라매컵 > 제1회 보라매컵 본선 G번