Minimizing the Largest Strongly Connected Component

An island has two rivers. River A has a cities numbered from 1 to a, and River B has b cities numbered from 1 to b. On each river, for any two cities with indices i and j such that i < j, there is a one‐way water route from city i to city j (but not in the reverse direction).

There are also m proposed flight routes connecting city x_i on River A and city y_i on River B. For each flight route, you can choose its direction: either from River A to River B or from River B to River A.

Define two cities to be connected if each can reach the other by a sequence of water routes and flight routes. In other words, they belong to the same strongly connected component (SCC) of the directed graph.

Your task is to choose a direction for every flight route such that the maximum size among all strongly connected components (i.e. the largest number of cities in any SCC) is minimized. It can be shown that by carefully choosing the directions the optimal answer is achieved.

Note: If you set all flight routes in one direction (for example, from River A to River B), then no cycle will be created because the water routes are only one‐way (from a smaller index to a larger index). In that case, every city remains isolated in terms of strong connectivity and the size of each SCC is 1. Hence, the answer is 1.

Determine this minimum possible value.

inputFormat

The first line contains three integers (a), (b), and (m) ((1 \le a,b \le 10^5), (0 \le m \le 10^5)).

Each of the next (m) lines contains two integers (x_i) and (y_i) ((1 \le x_i \le a), (1 \le y_i \le b)), indicating a flight route connecting city (x_i) on River A and city (y_i) on River B.

outputFormat

Output a single integer: the minimum possible size of the largest strongly connected component after assigning directions to all the flight routes optimally.

sample

3 3 1
2 2

1