아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

엠티

시간 제한1초메모리 제한256 MB

요약
각 학생이 지명한 한 명이 함께 타야만 버스에 탈 수 있을 때 조건을 어기지 않으면서 최대 k석까지 태울 수 있는 가장 많은 인원을 구합니다.
난이도

보통10점 중 7점

유형
그래프, 동적 계획법, 트리
정답자
아직 제출이 없습니다

문제

남규는 동기들과 엠티를 가려고 버스를 대절했다. 그런데 과사무실의 착오로 좌석 수가 잘못 잡혀서 동기 전원을 태울 수 없게 되었다. 사정을 들은 동기들은 서로 이런 말을 주고받았다.

재혁: 동우가 안 가면 나도 안 간다.
동우: 세종이가 안 가면 난 안 갈래.

좌석은 한정되어 있는데 저마다 다른 누군가가 가지 않으면 자기도 가지 않겠다고 하니 남규는 난감해졌다. 술을 너무 많이 사 둔 탓에 되도록 많은 인원을 데려가야 한다.

각 사람이 지목한 상대가 주어질 때, 아무의 조건도 어기지 않고 버스에 태울 수 있는 최대 인원을 구하시오.

입력

첫째 줄에 사람 수 nn과 버스에 태울 수 있는 사람 수 kk가 주어진다. (1≤k≤n≤10001 \le k \le n \le 1000)

둘째 줄에 정수 x1,x2,…,xnx_1, x_2, \dots, x_n이 순서대로 주어진다. (1≤xi≤n1 \le x_i \le n) xix_i는 xix_i번 사람이 버스에 타지 않으면 ii번 사람도 타지 않는다는 뜻이다.

출력

아무의 조건도 어기지 않고 버스에 태울 수 있는 최대 인원을 한 줄에 출력하시오. 한 명도 태울 수 없으면 0을 출력한다.

예제3

  1. 예제 1

    입력
    4 4
    1 2 3 4
    
    예상 출력
    4
    
  2. 예제 2

    입력
    12 3
    2 3 4 5 6 7 4 7 8 8 12 12
    
    예상 출력
    2
    
  3. 예제 3

    입력
    5 4
    2 3 1 5 4
    
    예상 출력
    3