Moving Chemicals
Time limit1sMemory limit1024 MB
Each lab holds n chemicals; swapping k pairs between them must avoid listed incompatible A-B pairs, with k at most n/2. Maximize k.
- Level
Medium7 of 10
- Topics
- Graph, Dynamic programming, Combinatorics, Brute force
- Solved
- No attempts yet
Problem
A company has decided to move the chemicals stored in its laboratories. The company has two laboratories (call them laboratory A and laboratory B), and each laboratory stores n kinds of chemicals. Because of space limits, each laboratory can hold only n kinds of chemicals, so some chemicals in laboratory A must be swapped with the same number of chemicals in laboratory B.
Changing the laboratory where a chemical is stored helps prevent the company's secrets from leaking, so the company wants to move as many chemicals as possible. There is a problem, though: some chemicals pose a risk of an accident if they are stored in the same laboratory. Accidents can also happen while chemicals are being moved, so the company has decided not to swap more than n/2 kinds of chemicals.
Given the list of chemical pairs that cannot be stored in the same laboratory, write a program to find the maximum number of kinds of chemicals that can be moved.
Input
The first line contains two integers n (1 ≤ n ≤ 200) and m (0 ≤ m ≤ n2). m is the number of pairs of chemicals that cannot be stored in the same laboratory. The next m lines each contain two integers a and b (1 ≤ a, b ≤ n). This means chemical a in laboratory A cannot be stored together with chemical b in laboratory B.
Output
On the first line, print the maximum number of kinds of chemicals that can be moved.
Hint
Swap chemicals 6, 7, 8 in laboratory A with chemicals 6, 7, 8 in laboratory B. In this case the chemicals in the two laboratories happen to have the same numbers, but the numbers do not have to match. Only the counts need to match.