Work Scheduling#4393
A certain number of night guards are available to protect the local junkyard from possible theft. These guards must be scheduled in pairs, so that each pair works together on a different night. The junkyard CEO has tasked you with writing a program that, given the possible pairings of guards, determines the maximum number of scheduled guards (the rest will be dismissed). Note that each guard can be scheduled with only one of their colleagues, and no guard can work alone.
The first line contains one number N \leq 222, the number of night guards. The following lines contain unordered pairs , where each such pair means that guards and can work together, because it is possible to find uniforms that suit both of them (the junkyard uses different parts of uniforms for different guards: helmets, pants, jackets. For example, it is impossible to put a small helmet on a guard with a big head or big shoes on a guard with small feet). The input ends at the end of file.
You should output one possible optimal assignment. On the first line, print the even number , the number of scheduled guards. Then output lines, each containing integers , denoting that guards and will work together.
Example 1