Intervals#2945
On the real line, there are intervals, each with endpoints at integer positions. These endpoints are not included in the intervals. You are given which pairs of intervals intersect and which do not. Using this information, determine the minimum possible total length of all intervals. Note that every interval must have length at least .
The first line contains two integers: (1 \leq n \leq 1234), the number of intervals, and (0 \leq m \leq n(n-1)/2), the number of pairs of intervals that intersect. The next lines contain pairs of indices of intersecting intervals. Intervals are numbered from to n-1. If a pair of intervals is not listed, then they do not intersect. It is guaranteed that it is possible to construct a set of intervals that matches the given information.
Print the minimum possible total length of all intervals. Intervals cannot have zero length.
Example 1