Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
28 kB
0
Indexable
Never
*** De ***
Hugo Đào Vàng
Hugo đào vàng trả nợ

Sau khi ăn trộm được mật của chị ong nâu và say sưa thưởng thức mật ngọt say đắm thì bất ngờ Hugo bị chị ong nâu phát hiện. Mặc dù đã thành khẩn nhận lỗi và xin lỗi chị ong nâu nhưng do đã đánh chén gần hết số mật đã ăn chộm nên chị ong nâu vẫn bắt Hugo phải bồi thường số mật đó. Hugo thì làm sao có thể kiếm mật được vì vậy Hugo phải đi đào vàng kiếm tiền để có tiền mua mật trả cho chị ong nâu.

Một cách tình cờ Hugo có được bản đồ của một khu vực chứa vàng, bản đồ được vẽ dựa trên một ma trận NxN. Trong ma trận có các điểm chứa vàng có thể khai thác (Tối đa 4 điểm). Hàng ngày Hugo sẽ phải đi tới mỏ vàng để khai thác và cuối ngày sẽ phải mang vàng trở về. Để tiết kiệm chi phí và thời gian, Hugo quyết định cắm trại trên gần mỏ vàng để tiện khai thác vàng. Hugo không thể di chuyển qua khu vực đá và không thể cắm trại trên đá, đồng thời Hugo cũng không thể cắm trại tại khu vực mỏ vàng, thời gian để Hugo di chuyển qua mỗi ô là 1 giờ.

Hãy giúp Hugo tìm địa điểm tối ưu để đi khai thác tất cả các mỏ vàng nhanh nhất.

Xem xét ma trận mỏ vàng 5x5 bên dưới:

1	1	0	0	0
1	x	0	0	0
1	1	0	0	0
1	1	1	2	1
1	1	1	0	2

X: Vị trí
2-Gold
0-Đá
1-Đường

 

Có 2 mỏ vàng, nếu Hugo cắm trại tại vị trí X, Hugo sẽ mất 4 giờ để đi tới mỏ vàng thứ 1, và 6 giờ để đi tới mỏ vàng thứ 2, vì vậy thời gian nhỏ nhất để Hugo đi khai thác vàng là 6 giờ, thời gian lớn nhất để đi khai thác của tất cả các mỏ vàng.

Xem xét ví dụ khác:

1	1	0	0	0
1	1	0	0	0
1	1	0	0	0
1	1	1	2	1
x	1	2	0	1
 
Thời gian là 4

1	1	0	0	0
1	1	0	0	0
1	1	0	0	0
1	1	x	2	1
1	1	2	0	1

Thời gian là 1

1	1	0	0	0
1	1	0	0	0
1	1	0	0	0
1	1	1	2	x
1	1	2	0	1

Thời gian là 3

 

Thời gian tối ưu với ma trận mỏ vàng trên là 1.

Một mỏ vàng được coi là không thể tiếp cận khi không thể đặt 1 vị trí cắm trại nào để đi khai thác vàng.

[Input]

Số trường hợp thử nghiệp T (T ≤ 50)

Mỗi TC :

 - Dòng đầu tiên chứa kích thước ma trận N (N ≤ 20) và số mỏ vàng G (2 ≤ G ≤ 4)

 - G dòng tiếp theo đưa ra vị trí R (hàng) & C (cột) của mỏ vàng (Chỉ số bắt đầu từ 1)

- N dòng tiếp theo là thông tin ma trận: 1 là có đường đi và vị trí mỏ vàng, 0 là đá (không thể đi qua).

 

[Output]

Dòng đầu tiên: In ra chi phí nhỏ nhất để đi từ trại tới điểm đào vàng xa nhất. Nếu không thể tiếp cận tất cả các mỏ vàng, in ra -1

Nếu có bất kỳ mỏ vàng nào không thể tiếp cận, bạn nên in ra vị trí của chúng trên mỗi dòng theo thứ tự đã nhập vào. Bạn nên đặt vị trí trại sao cho Hugo có thể tiếp cận được nhiều mỏ vàng nhất có thể. Ưu tiên các mỏ vàng xuất hiện trước theo thứ tự nhập.

Case #1

1

Case #2

2

Case #3

2

Case #11

1

4 3

4 5

6 10

Case #48

-1

Case #49

11

 

[Constraints]

- You can move on 4 directions (up/left/down/right)

- You can not setup the camp on gold mine location or rock

- You can go pass a gold mine then go to other gold mine

- You should place camp in order to Maximize the number of reachable gold mines

*** input ***
50
5 2
4 3
3 4
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
8 2
5 6
6 4
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
10 3
8 2
5 3
7 1
0 0 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 0
1 0 0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
8 3
1 2
2 8
5 8
0 1 0 0 0 0 0 0
0 1 0 1 1 1 1 1
0 1 0 1 0 0 0 1
0 1 1 1 0 0 0 1
0 1 0 1 0 0 0 1
0 1 0 1 1 1 1 1
0 1 0 0 1 0 0 0
0 1 0 0 1 0 0 0
10 4
9 6
1 9
7 5
6 6
1 1 1 1 1 0 0 1 1 1 
1 1 0 1 1 1 1 0 0 0 
0 1 0 1 1 0 1 1 1 1 
0 1 0 0 1 1 1 1 0 1 
0 1 0 0 1 0 1 1 1 1 
1 1 0 0 1 1 0 1 1 1 
1 1 0 0 1 1 1 1 1 1 
0 1 0 1 1 0 0 0 1 0 
1 0 1 0 1 1 1 1 1 0 
0 1 1 1 1 1 0 0 1 0 
10 3
10 4
6 7
4 5
0 0 1 0 0 0 1 0 1 0 
1 1 0 1 1 1 1 1 0 1 
1 1 0 1 1 0 1 1 0 0 
1 1 1 1 1 0 1 1 1 1 
0 1 0 1 0 1 1 1 0 1 
1 0 1 0 1 1 1 1 1 1 
0 0 0 0 0 1 1 0 1 1 
0 1 0 1 1 1 1 1 0 1 
1 0 0 1 1 1 1 1 1 0 
1 1 1 1 1 0 1 1 0 1 
10 3
8 8
6 9
7 8
0 1 1 1 0 0 0 0 1 1 
1 1 1 1 1 0 0 1 1 1 
1 1 1 1 1 0 1 1 0 1 
0 1 0 0 1 1 1 1 1 1 
0 0 0 1 0 1 0 1 1 1 
0 1 1 1 1 1 1 0 1 1 
0 0 0 0 1 1 1 1 1 1 
1 0 0 1 1 1 0 1 1 1 
0 1 0 1 1 1 1 1 1 1 
0 1 0 1 0 1 1 1 1 1 
10 3
5 2
8 2
4 6
1 1 1 0 0 1 1 1 1 1 
1 1 0 1 0 1 1 1 1 0 
1 1 0 1 1 1 0 1 1 1 
0 1 1 1 1 1 0 0 0 1 
0 1 1 0 1 0 1 1 1 1 
1 1 0 1 1 1 1 1 1 0 
0 1 0 1 1 1 1 1 0 1 
1 1 1 1 1 1 0 1 1 1 
1 1 1 0 1 1 1 1 1 0 
1 0 0 1 0 1 1 1 1 1 
10 4
8 3
1 2
9 5
5 7
1 1 1 1 1 1 1 1 1 1 
1 1 0 1 1 1 1 1 1 1 
1 1 0 1 1 1 0 1 1 1 
0 1 0 1 1 1 1 0 1 1 
0 0 0 1 1 0 1 0 1 0 
1 1 1 1 1 1 1 0 1 1 
1 1 1 1 1 1 1 1 1 1 
0 0 1 0 1 0 1 1 1 1 
1 1 1 0 1 1 1 1 1 1 
0 0 1 1 1 1 1 0 1 1 
10 2
8 4
1 10
1 0 1 1 0 1 1 1 0 1 
0 0 0 1 0 0 1 0 1 1 
1 1 0 0 1 1 0 0 1 1 
1 1 0 1 1 0 1 1 0 1 
1 1 1 1 0 1 1 1 1 0 
1 1 0 1 0 1 1 0 0 1 
1 1 0 1 1 1 0 1 1 0 
1 1 1 1 0 1 0 1 1 0 
1 0 1 0 1 0 1 1 1 1 
0 1 0 1 0 1 1 1 1 1 
10 4
3 4
4 3
4 5
6 10
1 0 0 1 1 0 0 0 1 0 
1 1 1 1 0 1 1 0 1 0 
1 0 0 1 0 1 1 1 0 1 
1 0 1 0 1 1 1 1 1 0 
0 1 0 0 1 1 1 1 0 0 
1 1 0 0 1 1 1 0 1 1 
1 0 0 1 0 1 0 1 1 0 
1 0 1 1 0 0 1 1 0 0 
1 1 1 1 1 1 1 1 0 1 
1 1 1 1 1 0 0 1 1 1 
10 2
4 6
4 8
0 0 0 1 1 0 0 1 1 1 
1 1 1 0 1 1 1 0 1 0 
1 0 1 1 0 1 1 0 1 0 
1 0 1 1 0 1 1 1 0 0 
1 1 1 1 0 1 1 1 1 1 
0 1 1 0 1 1 0 1 1 1 
1 0 1 0 1 1 1 0 1 1 
0 1 1 0 0 1 1 1 1 1 
0 0 1 0 0 1 0 1 1 0 
1 1 0 0 1 0 1 1 0 0 
10 3
6 6
2 5
6 8
0 1 1 1 1 1 1 0 1 1 
1 1 0 1 1 0 1 1 0 1 
0 1 0 1 0 1 1 0 1 1 
0 0 1 1 0 0 1 1 1 0 
1 1 0 1 1 1 1 0 0 1 
1 1 1 0 0 1 0 1 0 0 
1 0 0 0 0 0 0 1 1 1 
1 1 1 1 0 1 1 1 1 1 
1 1 1 0 1 1 0 1 0 1 
0 1 1 1 0 1 1 1 0 1 
10 4
3 2
6 7
3 9
7 9
0 0 0 1 0 1 0 0 0 1 
0 1 0 1 0 0 1 0 1 1 
0 1 1 1 0 1 0 1 1 0 
1 1 0 1 0 1 1 0 0 1 
0 1 1 1 0 1 1 1 0 1 
1 0 1 1 1 1 1 1 1 1 
0 1 1 0 1 1 1 1 1 1 
0 0 1 1 0 0 1 1 1 1 
1 1 1 1 0 1 1 1 0 1 
1 0 0 1 0 1 0 0 1 0 
10 4
1 7
2 4
9 10
7 2
1 1 0 1 1 0 1 1 1 1 
1 1 0 1 1 1 0 1 1 0 
1 1 0 1 0 1 0 0 1 1 
1 0 1 1 0 1 1 0 0 1 
1 0 0 0 0 0 1 1 1 0 
1 1 0 0 1 0 0 1 1 1 
0 1 1 1 1 1 1 0 1 0 
1 1 1 1 1 0 0 1 0 0 
0 1 0 1 1 0 0 1 0 1 
1 1 1 1 1 0 1 0 0 0 
10 2
2 2
3 6
0 1 1 1 0 1 0 1 1 1 
1 1 1 0 0 1 1 1 1 0 
0 0 0 0 1 1 0 1 1 0 
0 1 0 0 0 1 0 0 1 1 
1 1 1 1 1 1 0 1 0 1 
1 1 1 1 0 1 1 1 0 0 
1 1 0 0 1 1 1 1 1 0 
1 0 1 0 0 0 0 1 1 0 
0 1 0 1 1 1 1 1 1 1 
1 1 1 1 1 0 1 0 1 1 
10 4
1 4
9 5
4 3
1 6
0 0 1 1 1 1 1 1 0 1 
1 1 1 0 0 0 1 0 0 1 
1 1 1 0 1 0 1 0 0 0 
1 1 1 1 1 1 1 1 1 0 
0 1 0 1 0 0 1 1 1 0 
0 1 1 0 1 0 0 1 1 1 
1 1 1 1 1 1 0 0 1 1 
1 0 1 1 1 1 1 1 1 1 
1 1 1 0 1 1 1 1 0 1 
1 1 1 0 1 1 1 1 0 0 
10 2
10 10
10 6
1 1 1 0 1 0 1 1 1 1 
1 0 1 1 1 0 0 0 1 0 
1 1 1 1 0 0 1 1 1 0 
1 1 1 0 0 1 1 1 1 0 
0 1 0 1 0 1 0 0 0 1 
1 1 0 1 1 0 0 1 0 1 
1 0 1 1 1 0 0 0 0 1 
1 0 0 1 1 1 1 1 0 0 
0 1 1 1 1 1 1 0 1 0 
1 1 0 0 1 1 0 1 0 1 
10 3
6 8
9 6
6 5
0 1 0 0 1 1 0 1 0 1 
0 1 0 0 1 1 1 1 0 1 
1 0 1 0 0 1 1 1 1 1 
1 1 0 0 1 1 1 1 0 1 
0 0 1 0 0 0 1 1 1 0 
1 0 1 1 1 1 0 1 1 1 
1 1 1 1 0 0 1 0 1 1 
1 1 1 1 1 0 1 0 1 1 
0 1 0 0 1 1 1 1 0 0 
1 1 1 1 1 1 1 1 1 1 
10 3
9 4
4 2
9 10
1 1 1 0 0 1 0 1 1 0 
1 1 1 1 1 1 1 1 1 1 
1 0 1 1 1 1 1 0 0 0 
0 1 0 1 0 0 1 1 1 1 
1 1 1 1 1 1 1 1 0 1 
0 1 0 0 1 1 1 1 1 1 
1 1 0 0 0 1 1 1 1 0 
1 1 1 1 0 1 1 0 1 1 
0 1 1 1 1 1 1 1 1 1 
0 1 0 1 1 1 1 1 0 0 
12 4
8 4
6 3
12 5
5 7
1 0 1 1 0 1 0 0 0 0 1 1 
1 1 0 0 0 1 1 1 1 0 0 1 
1 0 1 0 0 0 0 1 1 0 1 1 
0 1 0 1 1 1 1 0 1 1 0 1 
0 0 0 1 1 0 1 1 0 1 0 0 
0 1 1 1 1 1 0 0 1 1 0 0 
1 1 1 0 1 1 1 1 0 1 1 0 
1 1 1 1 1 1 1 1 1 1 1 1 
1 1 0 1 1 0 0 1 1 1 1 1 
0 1 0 1 0 1 1 1 1 1 1 1 
1 1 1 1 1 0 1 0 1 0 1 1 
1 0 1 1 1 0 0 1 1 1 1 1 
12 2
6 11
6 12
1 0 0 0 1 1 0 1 1 0 1 1 
1 1 1 1 1 1 0 0 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 0 1 
1 1 0 0 1 0 1 1 0 0 1 0 
0 1 0 1 0 0 0 1 1 0 0 0 
1 0 1 0 1 1 1 1 1 0 1 1 
0 0 1 0 1 0 1 1 1 0 1 0 
1 0 1 0 1 0 0 0 0 0 1 0 
0 0 0 1 1 1 0 0 0 1 0 1 
0 1 1 1 1 1 1 0 0 0 0 1 
1 1 0 0 0 1 1 0 1 0 1 0 
1 1 0 1 0 0 1 0 0 1 1 1 
12 4
11 2
2 7
8 5
12 6
0 0 1 0 1 1 0 0 0 1 1 1 
1 0 1 1 0 0 1 1 0 1 1 1 
1 1 0 1 0 1 0 1 1 1 1 1 
0 1 1 0 1 0 1 1 1 1 0 1 
1 1 1 0 0 0 0 0 0 1 1 1 
1 1 0 1 1 1 1 1 1 1 1 0 
1 1 0 1 1 1 0 1 1 1 0 1 
0 1 0 0 1 1 1 1 1 1 1 0 
1 0 0 1 1 1 0 0 1 1 0 1 
0 0 1 0 1 0 1 1 1 0 1 1 
0 1 1 1 1 1 1 0 1 0 0 0 
1 0 0 0 0 1 1 0 1 1 1 0 
12 4
7 3
11 5
2 10
10 2
0 1 1 1 0 1 1 0 1 1 0 1 
1 0 1 1 1 0 1 1 1 1 0 0 
0 0 1 1 1 0 1 0 1 1 1 1 
1 1 0 1 1 1 0 1 1 1 1 0 
1 1 0 1 0 1 1 1 1 0 1 1 
0 1 0 0 0 0 1 0 1 1 1 0 
0 0 1 1 1 0 1 0 1 0 1 1 
1 1 1 1 0 0 1 1 1 1 1 1 
1 0 1 0 1 0 1 1 0 1 0 0 
0 1 1 1 1 1 1 1 1 0 0 0 
1 1 1 1 1 1 1 1 0 0 0 1 
1 0 1 0 1 0 1 1 0 1 1 1 
12 4
4 3
5 5
11 10
10 10
0 1 0 0 1 1 1 1 1 1 1 0 
1 1 1 0 1 1 0 1 1 1 0 0 
1 1 0 1 0 1 1 0 1 1 1 1 
0 0 1 1 0 1 1 1 1 0 1 1 
0 1 1 1 1 0 0 1 0 1 1 1 
1 1 1 0 1 0 0 0 0 0 0 0 
1 1 1 0 1 1 1 1 1 0 1 0 
1 1 1 0 1 1 1 0 1 1 0 1 
1 1 1 0 1 0 1 1 0 0 1 0 
1 1 1 1 1 1 1 1 0 1 0 1 
0 0 1 1 1 1 1 1 0 1 1 1 
1 0 0 1 1 0 1 1 1 0 1 1 
12 2
11 10
3 6
1 1 1 0 0 1 1 0 0 1 0 0 
1 1 0 1 1 1 0 1 1 1 1 1 
1 0 1 0 0 1 1 0 1 1 1 1 
1 1 1 1 0 1 1 1 1 1 0 0 
1 1 1 1 1 1 1 0 1 0 1 1 
0 1 1 1 0 1 1 1 1 1 1 1 
1 1 1 1 1 1 0 1 0 1 1 0 
1 1 0 1 1 0 0 1 0 1 1 1 
1 1 0 1 0 1 1 1 1 1 0 0 
1 1 0 0 1 0 1 1 1 1 1 0 
1 0 1 0 1 0 0 0 0 1 1 1 
1 1 0 1 1 1 0 1 1 1 0 1 
12 2
2 11
1 7
0 1 1 1 1 1 1 0 0 1 1 1 
1 1 0 0 1 0 1 0 1 1 1 1 
1 0 1 0 1 1 0 1 0 1 0 1 
1 1 0 1 0 1 0 0 1 1 1 1 
0 1 0 1 1 1 1 0 1 0 1 0 
1 1 1 1 1 1 1 1 0 0 1 0 
1 1 1 1 0 1 1 1 1 0 0 0 
1 1 0 1 0 0 0 1 1 1 0 1 
1 1 1 0 1 0 0 0 1 1 0 0 
1 1 0 1 0 0 1 1 1 1 1 0 
0 1 0 0 1 1 1 1 1 0 1 1 
1 1 0 1 1 1 0 0 1 1 0 0 
12 2
3 9
9 8
1 1 1 1 1 1 1 1 0 1 1 1 
1 1 1 1 1 0 1 1 0 0 1 1 
1 0 1 0 1 0 1 1 1 0 1 1 
0 1 1 1 1 0 1 1 0 1 1 0 
1 0 0 0 0 1 0 0 1 1 1 1 
0 1 1 1 1 1 1 0 0 0 1 1 
1 0 0 1 1 1 1 1 0 0 1 0 
1 1 1 0 1 0 0 0 1 1 1 1 
1 1 1 1 0 0 0 1 1 1 1 0 
1 1 0 1 1 0 0 1 0 1 0 0 
0 1 1 1 0 1 0 1 0 0 1 1 
0 0 0 1 1 1 1 0 0 1 1 0 
12 3
5 2
12 7
10 10
1 1 1 1 1 1 1 1 1 1 1 0 
1 1 0 1 1 1 0 1 0 0 0 1 
1 0 1 1 0 1 1 0 1 0 1 1 
0 1 1 0 1 1 0 1 1 1 1 1 
1 1 1 1 1 0 0 1 1 1 0 1 
1 0 1 1 1 0 1 0 1 0 1 1 
0 0 1 1 0 1 1 0 1 1 1 0 
0 0 0 1 0 1 0 1 1 0 1 1 
1 1 1 1 1 1 1 1 0 1 1 1 
1 0 0 1 0 0 0 1 0 1 1 1 
1 0 1 0 1 0 1 1 1 1 1 1 
0 0 1 1 0 1 1 0 0 0 0 1 
12 2
8 3
8 9
1 1 0 0 1 0 0 1 0 1 1 0 
0 0 1 1 0 0 0 1 1 1 0 0 
1 1 0 1 1 1 0 0 0 0 0 0 
1 1 1 0 0 0 0 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 0 1 1 0 0 1 0 1 1 
0 1 1 1 1 0 1 0 1 0 1 0 
1 0 1 1 1 1 1 1 1 0 0 0 
1 1 1 1 0 1 0 1 0 1 1 0 
1 1 1 1 1 1 0 0 1 0 0 1 
1 1 0 1 0 0 0 0 1 1 0 1 
1 1 0 1 0 1 1 1 0 1 0 0 
15 2
7 14
1 13
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 
1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 
1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 
0 1 1 0 1 0 1 0 1 1 0 1 1 1 1 
0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 
1 0 1 1 1 1 1 1 0 0 1 0 0 0 1 
0 1 0 0 1 0 1 1 1 0 1 1 1 1 1 
0 1 0 0 1 0 1 1 1 0 0 1 0 0 1 
1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 
0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 
1 1 1 0 1 0 1 1 1 0 1 1 0 1 0 
1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 
1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 
0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 
0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 
15 4
15 3
3 9
1 8
5 2
1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 
1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 
0 1 1 1 1 0 1 0 1 1 0 1 0 0 1 
1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 
0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 
1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 
1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 
1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 
0 1 0 1 1 0 1 0 0 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 
1 0 1 0 0 1 1 1 1 0 1 0 0 0 1 
1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 
1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 
15 4
2 8
14 14
5 8
3 4
1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 
1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 
1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 
0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 
0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 
1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 
1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 
0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 
0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 
1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 
1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 
15 3
11 15
12 3
9 2
0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 
0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 
1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 
1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 
1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 
0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 
0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 
1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 
0 1 1 1 0 1 1 1 1 0 1 1 0 1 1 
1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 
0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 
1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 
1 1 1 1 1 0 1 0 0 0 1 0 1 1 1 
1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 
0 1 0 0 1 1 0 1 0 0 0 0 1 1 1 
15 3
2 2
1 7
3 13
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 
1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 
0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 
1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 
0 1 0 1 0 0 1 0 0 0 1 1 1 0 1 
0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 
1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 
1 1 1 1 1 0 0 1 0 1 1 1 1 0 1 
1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 
1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 
1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 
0 1 1 1 1 0 1 0 0 1 0 1 1 0 1 
1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 
0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 
1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 
15 4
6 8
11 2
11 5
12 12
0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 
0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 
1 1 1 0 1 0 1 0 1 1 1 1 1 1 0 
1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 
1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 
0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 
0 1 1 0 1 1 0 0 1 0 0 1 1 0 1 
1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 
1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 
1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 
0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 
0 0 1 0 0 1 1 0 1 1 1 1 1 0 1 
1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 
15 4
6 10
4 15
15 8
2 9
1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 
1 1 1 0 0 1 1 0 1 0 1 0 1 1 0 
1 0 1 1 0 1 1 1 1 0 0 0 1 0 0 
1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 
1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 
1 0 1 1 1 0 1 1 0 1 1 0 0 1 0 
0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 
0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 
1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 
1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 
1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 
0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 
1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 
0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 
0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 
15 3
3 9
7 13
11 5
1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 
1 1 0 0 0 1 1 1 1 0 0 1 1 0 1 
0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 
1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 
0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 
1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 
1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 
1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 
0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 
0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 
1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 
1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 
0 1 0 1 1 0 1 1 1 1 1 1 0 0 0 
1 1 0 0 1 0 1 1 1 1 1 0 1 1 1 
1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 
15 2
7 11
10 8
1 0 1 1 1 1 0 0 1 0 1 1 0 1 1 
1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 
1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 
1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 
1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 
1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 
1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 
1 1 1 1 0 1 1 0 1 1 1 0 1 0 1 
1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 
0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 
1 1 1 1 1 0 1 1 0 0 1 0 1 0 0 
0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 
1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 
0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 
15 3
12 8
6 8
10 13
1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 
1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 
1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 
1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 
1 0 1 1 1 1 1 1 1 0 1 1 0 1 0 
0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 
1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 
1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 
1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 
1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 
1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 
1 0 1 1 0 1 0 0 0 1 0 0 1 1 1 
20 2
5 14
18 17
0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 
1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 
1 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 
1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 
1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 
1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 
0 0 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 
1 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 
1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 
1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 
1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 
1 1 1 0 0 1 0 1 1 1 0 0 1 1 1 1 0 1 0 1 
1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 
1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0 
1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 
1 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 
1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 
0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 
0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 
20 3
12 4
20 4
17 2
1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 
1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 
1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 
0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 
1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 
1 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 0 
1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 
1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 
1 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 
1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0 
0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 1 
1 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 
0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 
0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 
1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1 0 
0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 1 
0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 
0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 
1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 
20 2
18 14
8 13
0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 
0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 
0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 
1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1 
1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 
1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 
1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 
1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 
1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 
1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 
1 1 1 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 
0 0 1 1 0 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 
0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 
0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 
0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 
0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 
1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 
1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 0 
1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 0 
20 2
6 16
16 6
1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 
1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 
1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 
1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 1 
1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 
0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 
1 0 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 
0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 
1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 
1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 
1 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 
1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 1 
1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 
1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 
0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 
0 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 
1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 
1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 
1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 
1 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 1 1 1 
20 4
20 13
15 16
13 9
3 9
0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 0 1 
1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 
0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 
1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 
1 1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 
1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 0 
1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 
1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 
1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 
1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 
0 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1 
0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 
0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 
0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 0 0 
1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 
0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 
0 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1 1 
0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 
1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 
0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 
20 3
18 2
18 11
11 16
1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 1 
0 0 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 
1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 0 1 
0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 
1 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1 
1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 0 
1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 
0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 
0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 
1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 
1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1 
0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1 1 
0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 
0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0 
1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 
1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 1 1 1 
0 0 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1 
0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 
1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 
0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 1 
20 3
8 4
5 10
9 14
1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 
0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 
1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 
0 1 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 0 
1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 
1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 
0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 
0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 
0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 
1 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 
0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 
1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 1 
1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 
1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1 
0 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 
1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 
1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 
0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 
0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 
20 2
9 4
1 10
1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 
1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 
1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 
1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 
1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 
1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 
0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 
1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 0 
1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 
1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 
0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 0 
1 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 
1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 
1 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 
1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 
1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 
1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 
1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 
0 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 
20 4
2 10
12 6
8 17
1 3
1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 
0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 
0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 
1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 
0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 
1 1 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1 
1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 
1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 
1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 0 0 
0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 
1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 
1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 
1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 
1 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 
1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 
1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 1 1 1 
1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 
20 2
17 2
20 20
0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 1 
1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 
0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 1 0 
1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 
0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 
1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 1 0 0 1 
1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 1 
1 1 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 
1 0 1 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 
1 1 0 0 0 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 
1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 
0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 
1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 
0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 
1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 
1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 1 0 
0 1 0 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 
0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 
0 1 1 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 
0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 1

*** output ***
Case #1
1
Case #2
2
Case #3
2
Case #4
7
Case #5
3
1 9
Case #6
8
Case #7
2
Case #8
4
Case #9
6
Case #10
1
8 4
Case #11
1
4 3
4 5
6 10
Case #12
1
Case #13
4
6 8
Case #14
6
3 9
Case #15
1
1 7
9 10
7 2
Case #16
1
3 6
Case #17
8
Case #18
1
10 10
Case #19
3
6 8
Case #20
7
Case #21
7
Case #22
2
Case #23
10
Case #24
9
Case #25
2
11 10
10 10
Case #26
6
Case #27
1
2 11
Case #28
1
9 8
Case #29
8
Case #30
3
Case #31
5
Case #32
10
Case #33
12
Case #34
12
Case #35
5
2 2
Case #36
13
Case #37
12
6 10
4 15
Case #38
8
Case #39
3
Case #40
11
Case #41
1
5 14
Case #42
8
Case #43
1
18 14
Case #44
10
Case #45
10
20 13
Case #46
8
18 2
Case #47
7
Case #48
-1
Case #49
11
Case #50
1
17 2

*** code ***
#include<iostream>
using namespace std;
#define cons 25
int n,so_movang;
int gold_x[cons];
int gold_y[cons];
int arr_map[cons][cons];
int index_gold[cons][cons];
int maxmax,minmin;
bool kiem_tra[cons];
bool kiemtra_temp[cons];
int min_index;
int dem_gold;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct Queue
{
	int rear,front;
	int arr_data[100000];
	Queue()
	{
		rear = front = 0;
	}
	bool isEmpty()
	{
		return rear == front;
	}
	void push(int a)
	{
		arr_data[rear] = a;
		rear++;
		rear = rear % 100000;
	}
	int pop()
	{
		int a = arr_data[front];
		front++;
		front = front % 100000;
		return a;
	}
};
void BFS(int vt_hang,int vt_cot)
{
	for (int i = 0; i < so_movang; i++)
	{
		kiemtra_temp[i] = false;
	}
	maxmax = 0;
	dem_gold = 0;
	int check_BFS[cons][cons];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			check_BFS[i][j] = -1;
		}
	}
	Queue Q = Queue();
	Q.push(vt_hang);
	Q.push(vt_cot);
	check_BFS[vt_hang][vt_cot] = 0;
	while (!Q.isEmpty())
	{
		int x = Q.pop();
		int y = Q.pop();
		for (int i = 0; i < 4; i++)
		{
			int hang = x + dx[i];
			int cot = y + dy[i];
			if(hang>=1 && hang<=n && cot>= 1 && cot<=n && arr_map[hang][cot] !=0 && check_BFS[hang][cot] == -1)
			{
				check_BFS[hang][cot] = check_BFS[x][y] + 1;
				Q.push(hang);
				Q.push(cot);
				if(arr_map[hang][cot] == 9)
				{
					dem_gold++;
					kiemtra_temp[index_gold[hang][cot]] = true;
					if(check_BFS[hang][cot] > maxmax )
					{
						maxmax = check_BFS[hang][cot];
					}
				}
			}
		}
	}
}
int main()
{
	// freopen("input.txt","r",stdin);
	int th;cin>>th;
	for (int tc = 1; tc <= th; tc++)
	{
		cin >> n >> so_movang;
		for (int i = 0; i < so_movang; i++)
		{
			cin >> gold_x[i] >> gold_y[i];
			index_gold[gold_x[i]][gold_y[i]] = i;
			kiem_tra[i] = false;
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				cin >> arr_map[i][j];
			}
		}
		for (int i = 0; i < so_movang; i++)
		{
			arr_map[gold_x[i]][gold_y[i]] = 9;
		}
		maxmax =0;
		minmin = 999999;
		int sl = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if(arr_map[i][j] == 1)
				{
					BFS(i,j);
					if(dem_gold > sl)
					{
						sl = dem_gold;
						minmin = maxmax;
						for (int k = 0; k < so_movang; k++)
						{
							kiem_tra[k] = kiemtra_temp[k];
						}
					}
					else if(dem_gold == sl)
					{
						if(maxmax != 0)
						{
							if(minmin > maxmax)
							{
								minmin = maxmax;
								for (int k = 0; k < so_movang; k++)
								{
									kiem_tra[k] = kiemtra_temp[k];
								}
							}
						}
					}
				}
			}
		}
		cout << "Case #" << tc << endl;
		if(minmin == 999999)
		{
			cout << -1 << endl;
		}
		else
		{
			cout << minmin << endl;
			for (int i = 0; i < so_movang; i++)
			{
				if(kiem_tra[i] == false)
				{
					cout << gold_x[i] << " " << gold_y[i] << endl;
				}
			}
		}
	}
	return 0;
}