Problem K
Conveyor Belts

Your factory has $N$ junctions (numbered from $1$ to $N$) connected by $M$ conveyor belts. Each conveyor belt transports any product automatically from one junction to another junction in exactly one minute. Note that each conveyor belt only works in one direction. There can be more than one conveyor belt connecting two junctions, and there can be a conveyor belt connecting a junction to itself.

There are $K$ producers (machines which produce the products) located at the first $K$ junctions, i.e. junctions $1, 2, \ldots , K$. The producer at junction $j$ produces an product each minute $(x \cdot K + j)$ for all integers $x \ge 0$ and $j = 1, 2, \ldots , K$. All products are transported immediately via the conveyor belts to the warehouse at junction $N$, except for those produced at junction $N$ (if any). Items produced at junction $N$ are directly delivered to the warehouse (there is no need to use the conveyor belts).

At each junction, there is a robot deciding which conveyor belts the incoming product should go to in a negligible time (instantly). The robots can be programmed such that all products produced by a producer are always delivered to the warehouse via the same route. Once the robots are programmed, the routing can no longer be changed. Items from different producers may have the same or different routes.

A prudent potential investor comes and wants to inspect the factory before making any decision. You want to show to the potential investor that your factory employs a good risk management policy. Thus, you want to make sure that each conveyor belt only transports at most one product at any time; i.e. two products cannot be on the same conveyor belt at the same time. On the other hand, there is no limit on the number of products at the junctions (the robots have a lot of arms!). To achieve this, you may turn off zero or more producers, but you still want to maximize the production, hence, this problem.

Find the maximum number of producers that can be left running such that all the produced products can be delivered to the warehouse and each conveyor belt transports at most $1$ product at any time.

Input

The first line contains three integers $N$, $K$, and $M$ ($1 \le K \le N \le 300$; $0 \le M \le 1\, 000$) representing the number of junctions, the number of producers, and the number of conveyor belts, respectively.

The next $M$ lines, each contains two integers $a$ and $b$ ($1 \le a, b \le N$) representing a conveyor belt connecting junction $a$ and junction $b$ with the direction from $a$ to $b$.

Output

The output contains an integer denoting the maximum number of producers which can be left running such that all the produced products can be delivered to the warehouse and each conveyor belt transports at most one product at any time.

Explanation

In Sample Input $1$, $N = 4$, $K = 2$, $M = 3$, and the directed edges are $\{ (1,3)$, $(2,3)$, $(3,4)\} $. There is only one possible delivery route for each producer, i.e. $1 \rightarrow 3 \rightarrow 4$ for producer $1$, and $2 \rightarrow 3 \rightarrow 4$ for producer $2$. Both producers are using conveyor belt $(3,4)$, however, the products from producer $1$ are on the conveyor belt $(3,4)$ on minutes $2, 4, 6, \dots $ (even minutes), while the products from producer $2$ are on the conveyor belt $(3,4)$ on minutes $3, 5, 7, \dots $ (odd minutes). Therefore, both producers can be left running.

In Sample Input $2$, $N = 5$, $K = 2$, $M = 4$, and the directed edges are $\{ (1,3)$, $(3,4)$, $(2,4)$, $(4,5)\} $. Similar to the previous example, there is only one possible delivery route for each product produced by each producer. In this example, only one producer can be left running as products from both producers ($1$ and $2$) are on the conveyor belt $(4,5)$ at the same time if both are running.

4 2 3
1 3
2 3
3 4

2

5 2 4
1 3
3 4
2 4
4 5

1

5 2 6
1 4
2 3
3 4
4 5
2 4
3 3

2