TLE '17 Contest 1 P5 - Cake

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 0.75s
Memory limit: 256M

Author:
Problem types
Flaco thinks that this cake design is too basic.

Fax McClad, Croneria's most friendly bounty hunter, has been busy preparing for his wingmate Flaco Lombradi's birthday! Fax will give him a very large cake. This is an unusual cake, so certain conditions must be met.

The cake can be divided into an R by C grid where every cell is either empty or contains cake. Rows are labelled from 1 to R, and columns are labelled from 1 to C. Every row and column has cake in it.

Also, the entire cake must be connected. In other words, it is possible visit the entire cake by moving only up, down, left, or right, and not entering any empty cell.

Since this is Flaco's cake, he suggests a specific cake design in the following format.

  • On the i^{th} row, there should be cake along the cells c_i, \dots, d_i, and the rest of the row is empty.
  • On the j^{th} column, there should be cake along the cells r_j, \dots, s_j, and the rest of the column is empty.

Given Flaco's design, please determine if the design makes sense! A design makes sense if the cake is connected, and it is clear whether a cell is empty or contains cake.

Input Specification

The first line contains two integers R and C.

On the next R lines, the i^{th} line will contain c_i and d_i (1 \le c_i \le d_i \le C).
On the next C lines, the j^{th} line will contain r_j and s_j (1 \le r_j \le s_j \le R).

Output Specification

Print sense if Flaco's design makes sense.

Otherwise, print nonsense. On the next line, print one of the two following choices:

  • x y, where 1 \le x \le R and 1 \le y \le C. This means that the cell at row x, column y is unclear.
  • unconnected, which means that the cake is not connected. Do not use this choice if there is an unclear cell.

Note: If there are multiple unclear cells, any example will be accepted.

Subtasks

Subtask Percentage Additional Constraints
1 30 1 \le R,C \le 10
2 20 1 \le R,C \le 1\,000
3 50 1 \le R,C \le 10^5

Sample Input 1

2 3
1 3
1 3
1 2
2 2
1 2

Sample Output 1

nonsense
1 2

Explanation 1

Cake 1 1, 2 2, 2 1, 2
1, 3 C ? C
1, 3 C C C

It is unclear whether the cell at row 1, column 2 is empty or contains cake.

Sample Input 2

2 2
2 2
1 1
2 2
1 1

Sample Output 2

nonsense
unconnected

Explanation 2

Cake 2 2, 2 1, 1
2, 2 C
1, 1 C

The cake is not connected.

Sample Input 3

3 4
1 1
1 4
3 4
1 2
2 2
2 3
2 3

Sample Output 3

sense

Explanation 3

Cake 3 1, 2 2, 2 2, 3 2, 3
1, 1 C
1, 4 C C C C
3, 4 C C

The cake is connected, and it is clear whether a cell is empty or contains cake.


Comments

There are no comments at the moment.