A building belongs to a company with many departments. One department can have many rooms and the departments can share the rooms.

Also in this company only one department works at a time and all members of the department work together always. (So at a particular time, only one department is in the building and all the rooms corresponding to the departments have their lights on. Rest of the rooms have their lights off.)

Now the task is to find the minimum number of rooms to look such that given the data about the lights in those rooms you can correctly predict which department is working.

Data: — the building is in the form of a 2d matrix, where a cell (i,j) corresponds to a room.

Example : — —

Building of size 3*3

Room (0,0)    shared by    department 1,4,3
Room (0,1)    shared by    department 2,3
Room (0,2)    shared by    department 1,5

Room (1,0)    shared by    department 5,4
Room (1,1)    shared by    department 2
Room (1,2)    shared by    department 3,6

Room (2,0)    shared by    department 2,1,4,6
Room (2,1)    shared by    department 5,6
Room (2,2)    shared by    department 2,3,6,4

Say at a particular day when department 1 is working, all the remaining departments are on leave and rooms (0,0),(0,2),(2,0) always have their lights on. Rest of room lights are off on that day.

So what is the minimum number of rooms to look to find out which department is working on that day?

Another example : —
If we have only two departments and a 2*3 building : -

(0,0) — 1,2
(0,1) — 1
(0,2) — 1

(1,0) — 2
(1,1) — 1
(1,2) — empty

So just by looking at room (1,1) we can say which department is working. So answer here is 1.

The input is number of departments, and the room ownership data. Rooms can also be not owned by any department.