Heros

회사가 최신 게임을 막 출시했습니다. 은하를 떠도는 떠돌이 퀘이사 사냥꾼 헤로사(herosa)의 모험은 판매가 좋고 평가도 괜찮습니다. 일부 플레이어는 게임 메커니즘이 너무 복잡하다고 불평할 뿐입니다. 실제 제작 과정을 모르는 것은 다행입니다. 잠 못 이룬 밤, 불량한 식사, 긴장된 분위기, 그리고 중요한 직원 한 명을 대신해야 했던 난수 생성기가 있었다는 사실을 말입니다. 이 모든 일은 영원히 드러나지 않는 편이 낫습니다.

게임 중 플레이어 캐릭터는 $n$개의 스킬 중 하나를 배울 수 있습니다(우주선 조종, 원소 마법, PHP 프로그래밍 등). 스킬들은 의존 관계 네트워크로 연결되어 있습니다. $m$개의 쌍 $(x, y)$가 있는데, 스킬 $y$는 스킬 $x$를 안 뒤에야 배울 수 있다는 뜻입니다. 의존 관계 네트워크에는 순환이 없습니다. 즉 어떤 스킬을 배우려면 그 스킬 자신을 먼저 알아야 하는 경우는 없습니다. 형식적으로 스킬들은 방향 비순환 그래프(DAG)를 이룹니다.

퇴사한 직원을 대신했던 난수 생성기를 기억하십니까? 이 프로그램이 스킬 네트워크를 만들었습니다. 먼저 스킬에 $1, 2, \ldots, n$의 번호를 무작위로 붙였습니다. 그다음 $x < y$인 서로 다른 쌍 $(x, y)$를 $m$개 무작위로 뽑아 의존 관계를 만들었습니다. 이 덕분에 개발자들의 끝없는 논쟁이 끝났고 제작 속도도 크게 빨라졌습니다. 그리고 당신은 이 생성기를 이달의 직원으로 선정하는 일을 맡게 되었습니다.

스킬 네트워크의 복잡도는 네트워크에서 찾을 수 있는 가장 긴 사슬의 길이입니다. 즉 각 스킬이 바로 앞 스킬을 요구하는 가능한 가장 긴 수열의 길이입니다. 복잡도가 지나치게 높으면 플레이어가 게임 메커니즘을 파악하기 어렵고, 네트워크 도식도 화면에서 보기 나빠집니다. 현재 구조를 이해하는 사람은 아무도 없습니다(증언하려 들지 않는 난수 생성기는 제외). 그래서 과감한 결정이 내려졌습니다. 스킬 $k$개를 모든 의존 관계와 함께 삭제해서, 남은 네트워크의 복잡도를 가능한 한 최대로 낮추라는 것입니다.

첫 줄에 정수 $n$, $m$, $k$가 주어집니다($1 \le n \le 300$, $0 \le m \le 400$, $0 \le k \le \min(n, 4)$). 각각 현재 스킬 수, 의존 관계 수, 삭제할 스킬 수입니다. 스킬은 1부터 $n$까지 번호가 붙어 있습니다. 이어지는 $m$개의 줄에는 정수 $x$와 $y$($1 \le x < y \le n$)가 주어집니다. 이는 스킬 $y$를 배우기 전에 스킬 $x$를 알아야 한다는 뜻입니다. 의존 관계는 문제에서 설명한 방법으로 무작위 생성되었다고 가정해도 됩니다.

스킬을 최대 $k$개 삭제한 후 남은 스킬 네트워크의 복잡도로 가능한 최솟값을 한 정수로 출력합니다.