题目描述

​ 给定 $n$ 个不同的正整数 $a_0,a_1,\cdots ,a_{n-1}$，我们可以在不排序的情况下找到这个数组第$k$大的数，这个问题存在时间复杂度线性的随机算法和确定性算法，但是仅仅线性并不能满足对效率的追求。

​ 我们定义一个算法的复杂度为该算法执行的两个元素大小比较的次数。 现在，你需要设计一个算法，使得最坏情况下的比较次数最少。

​ 比如，当 $n=3,k=1$ 时，最优算法的$C++$ 代码如下：

double selection(double a[3], int k = 1){
	if(a[0] < a[1]){
		if(a[0] < a[2]){
			return a[0];
		}else{
			return a[2];
		}
	}else{
		if(a[1] < a[2]){
			return a[1];
		}else{
			return a[2];
		}
	}
}

​ 这个算法最坏情况下会使用两次比较。

​ 你现在想解决一个更一般的问题，在已知了$l$对元素之间的大小关系的前提下，最优算法的最坏复杂度是多少？

输入格式

​ 第一行三个正整数 $n,k,l$。

​ 接下来$l$行每行两个整数 $x,y$, 表示已知 $a_x<a_y$.

输出格式

​ 输出一行一个整数，表示答案。

样例输入 1

3 2 0

样例输出 1

3

样例输出 2

7 2 5
0 6
3 6
4 6
2 0
0 5

样例输出 2

5

数据范围与提示

Subtask 1 (5 pts)

​ $n \le 4$

Subtask 2 (11 pts)

​ $n\le 5$

Subtask 3 (14 pts)

​ $n \le 6$

Subtask 4 (15 pts)

​ $n\le 7$

Subtask 5 (20 pts)

​ $l=0$

Subtask 6 (35 pts)

​ 无特殊限制

​ 对于所有数据，$2\le n\le 8,1\le k\le n,0\le l\le n$