paintbyrectangles

Paint by Rectangles

After her previous artwork was met with critical acclaim, Bessie was offered a job designing painting sets. She designs these paintings by choosing \(1 \leq N \leq 10^{5}\) axis-aligned rectangles in the plane such that no two edges are collinear. The boundaries of these rectangles define the boundaries of the painting's colored regions.

Still being an avant-garde artist, Bessie decides that the painting should resemble a Holstein cow. More specifically, each region formed by the rectangles is colored either black or white, no two adjacent regions have the same color, and the region outside of all the rectangles is colored white.

After choosing the rectangles, Bessie would like you to output one of two things based on a parameter \(T\):

• If \(T=1\), output the total number of regions.
• If \(T=2\), output the number of white regions followed by the number of black regions.

Limits

\(1 \leq N \leq 10^5\)

Subtasks #	Score	Constraints
1	9	\(1 \leq N \leq 10^3\)
2	14	No two rectangle boundaries intersect
3	14	\(T = 1\) The boundaries of all rectangles are connected
4	14	\(T = 2\) The boundaries of all rectangles are connected
5	24	\(T = 1\)
6	25	\(T = 2\)

Input format

The first line contains \(N\) and \(T\).

The next \(N\) lines each contain the description of a rectangle in the form \((x_1,y_1),(x_2,y_2)\) where \(1 \leq x_1 < x_2 \leq 2N\) and \(1 \leq y_1 < y_2 \leq 2N\). \((x_1,y_1)\) and \((x_2,y_2)\) are the bottom left and top right corners of the rectangle respectively.

It is guaranteed that all the \(x_i\) form a permutation of \(1 \ldots 2N\), and the same holds for all the \(y_i\).

Output format

A single integer if \(T=1\), otherwise two separated by spaces.

Samples

Sample Input 1	Sample Output 1
2 1 1 1 3 3 2 2 4 4	4

There are two white regions and two black regions, for a total of four regions. The boundaries of all rectangles are connected, so this input would satisfy the conditions of subtask 3.

Sample Input 2	Sample Output 2
5 2 1 5 3 6 5 4 7 9 4 1 8 3 9 8 10 10 2 2 6 7	4 5

The boundary of the rectangle in the upper-right is not connected to the rest of the boundaries, so this input would not satisfy the conditions of subtask 4.