Ezzat and Grid solution codeforces
Moamen was drawing a grid ofrows and columns containing only digits and . Ezzat noticed what Moamen was drawing and became interested in the minimum number of rows one needs to remove to make the grid beautiful.
A grid is beautiful if and only if for every two consecutive rows there is at least one column containingin these two rows.
Ezzat will give you the number of rows, and segments of the grid that contain digits . Every segment is represented with three integers , , and , where represents the row number, and and represent the first and the last column of the segment in that row.
For example, if, , and the segments are , , , , , , then the grid is:
The first line contains two integersand ( ).
Each of the nextlines contains three integers , , and ( , ). Each of these lines means that row number contains digits in columns from to , inclusive.
Note that the segments may overlap.
In the first line, print a single integer— the minimum number of rows that should be removed.
In the second line printdistinct integers , representing the rows that should be removed ( ), in any order.
If there are multiple answers, print any.
3 6 1 1 1 1 7 8 2 7 7 2 15 15 3 1 1 3 15 15
5 4 1 2 3 2 4 6 3 3 5 5 1 1
3 2 4 5
In the first test case, the grid is the one explained in the problem statement. The grid has the following properties:
- The -st row and the -nd row have a common in the column .
- The -nd row and the -rd row have a common in the column .
As a result, this grid is beautiful and we do not need to remove any row.In the second test case, the given grid is as follows: