给定 $n$ 个不同的数，我们可以在不进行排序的情况下输出第 $k$ 小的数。这个问题被称为选择问题（selection problem），并且可以在线性时间内解决。有些人认为现有的选择算法在实际应用中太慢了，因此有一种猜想：每当你遇到一个使用选择算法作为构建模块的算法时，都可以放心地用快速排序过程来代替选择算法。然而，这个猜想似乎并不成立。

Bob 试图回答上述猜想是否有效，但这被证明是一个复杂的问题，需要大量的试错实验。在经历了一些失败的尝试后，他决定首先专注于寻找实现选择算法的最佳方法。也就是说，要找到一种以最少比较次数实现选择的算法。我们假设 $n$ 个输入数字都是不同的。对于 $n=3$ 和 $k=1$，解决选择问题的一种最优算法如下所示：

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];
}
}
}

对于所有可能的 $(a[0], a[1], a[2])$，上述选择函数最多使用 2 次比较。事实上，如果输入数字之间的相对顺序只能通过比较来推断（即基于比较的算法），那么 2 次比较就是最优的。因此，对于 $(n, k) = (3, 1)$，选择函数的复杂度为 2。现在，Bob 正在考虑一个更通用的问题，即在调用选择函数之前，已知输入中某些对之间的比较结果。选择函数的复杂度定义为：在任何可能的相容输入数组上，最优的基于比较的算法所需的最坏情况比较次数。也就是说，Bob 想知道在给定 $n$、$k$ 以及 $n$ 个输入数字之间的一些相对顺序的情况下，选择函数的复杂度是多少。

输入格式

第一行包含三个整数 $n$、$k$ 和 $\ell$。接下来有 $\ell$ 行。随后的每一行包含两个整数 $x$ 和 $y$（其中 $0 \le x, y \le n-1$），表示在调用选择函数之前，已知 $a[x]$ 和 $a[y]$ 之间的相对顺序为 $a[x] < a[y]$。

输出格式

给定 $n$、$k$ 以及给定的 $\ell$ 对数字之间的相对顺序，输出选择函数的复杂度。

数据范围

• $1 \le n \le 8$
• $1 \le k \le n$
• $0 \le \ell \le n$
• 给定的 $\ell$ 对数字之间的相对顺序是相容的。

样例

样例输入 1

3 2 0

样例输出 1

3

样例输入 2

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

样例输出 2

5