TLE '17 Contest 1 P5 - Cake

View as PDF

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 by grid where every cell is either empty or contains cake. Rows are labelled from to , and columns are labelled from to . 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 row, there should be cake along the cells , and the rest of the row is empty.
• On the column, there should be cake along the cells , 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 and .

On the next lines, the line will contain and .
On the next lines, the line will contain and .

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 and . This means that the cell at row , column 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.

1 30
2 20
3 50

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 , column 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.