Dorm Party

Time limit15sMemory limit1024 MB

Summary

Given a bipartite interest graph, pick a minimum set of edges to dance so that no edge joins two undanced vertices.

Level: Hard8 of 10
Topics: Graph, Dynamic programming, Bit manipulation, Brute force
Solved: No attempts yet

Problem

In an ordinary dormitory two students share a room: the freshman Jack and the party animal Jude. One day Jude gets the idea of hosting a party in their room. Jack, on the other hand, likes peace and quiet, which is already hard to come by in a dorm. Since Jude has a great many friends, the mere thought of a party in their 18 m² room makes Jack shiver.

Jude wants to invite $N$ girls and $M$ boys to the party. Each girl is interested in some (possibly empty) set of boys, and exactly those boys are interested in that girl (interest is always mutual). To liven things up, Jude wants to arrange as many dancing pairs as possible, but a pair may dance only if the two are interested in each other.

Jack is afraid that a successful party will inspire Jude to throw more of them, and the success of a party is measured by its noise. First, a dancing guest is louder than a non-dancing one. Second, if two people who are not yet dancing are interested in each other, they will spontaneously pair up and start dancing — and, proud of their initiative (and a little drunk), they will be extra loud. Jack wants to prevent such spontaneous pairs at all costs while keeping the noise minimal. In other words, he wants an arrangement of dancing pairs in which no two non-dancing people are interested in each other (so that no new pair can form on its own), using as few dancing pairs as possible.

Determine the minimum number $S$ of dancing pairs in such an arrangement.

Input

The first line contains the number of girls $N$ ( $1 \le N \le 19$ ), the number of boys $M$ ( $1 \le M \le 19$ ), and the number of mutually interested pairs $K$ ( $0 \le K \le N \cdot M$ ). Each of the next $K$ lines contains two integers $A_i$ ( $1 \le A_i \le N$ ) and $B_i$ ( $1 \le B_i \le M$ ), meaning that girl $A_i$ and boy $B_i$ are interested in each other. No pair is listed more than once.

Output

Print a single integer $S$ : the minimum possible number of dancing pairs in an arrangement where no two non-dancing people are interested in each other.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
3 3 0
```
Expected output
```
0
```
Example 3
Input
```
1 1 1
1 1
```
Expected output
```
1
```
Example 4
Input
```
2 2 4
1 1
1 2
2 1
2 2
```
Expected output
```
2
```
Example 5
Input
```
4 1 4
1 1
2 1
3 1
4 1
```
Expected output
```
1
```
Example 6
Input
```
4 4 4
1 1
2 2
3 3
4 4
```
Expected output
```
4
```