Gridev's Protocol

Time limit2sMemory limit512 MB

Summary

Given M error cells on an N by N grid, find the fewest row or column clears (each allowed when the line has at most K errors) that remove every error, or report -1.

Level: Medium6 of 10
Topics: BFS, Graph, Greedy
Solved: No attempts yet

Problem

Seongjun is a robot that solves any problem with ease. Geungsu, jealous of him, damaged his circuit board while he was asleep.

Fortunately, Seongjun has a self-repair protocol, and he plans to use it to fix himself. Seongjun's circuit board is an $N \times N$ grid, and currently there are errors at $M$ coordinates $(x_i, y_i)$ . Seongjun can repeat the following two kinds of actions.

For every row with at most $K$ errors, remove all errors in that row. The state of a row with more than $K$ errors does not change.
For every column with at most $K$ errors, remove all errors in that column. The state of a column with more than $K$ errors does not change.

Seongjun wants to repair himself quickly and get revenge on Geungsu. Find the way to remove all errors with the fewest actions.

Input

The first line contains the size of the board $N$ , the number of errors $M$ , and the maximum number of errors $K$ that can be repaired in one row or column, separated by spaces. ( $1 \le N, M, K \le 2\times10^5$ )

From the second line to the $(M+1)$ -th line, the positions of the errors $(x_i, y_i)$ are given, separated by spaces. ( $1 \le x_i, y_i \le N$ )

No error position is given more than once.

Output

Print the minimum number of actions needed to remove all errors. If there is no way to remove all errors, print -1.

Examples3

Example 1
Input
```
3 4 1
1 1
2 1
2 2
3 2
```
Expected output
```
2
```
Example 2
Input
```
2 4 1
1 1
2 1
1 2
2 2
```
Expected output
```
-1
```
Example 3
Input
```
1 1 1
1 1
```
Expected output
```
1
```