The Settlers of Catan

Settlers of Catan, một trò chơi của người Đức ở năm 1995, người chơi tham gia vào cuộc cai trị một hòn đảo bằng việc xây dựng các con đường, các khu định cư, và các thành phố qua các vùng hoang dã chưa được thám hiểm.

Bạn được một công ty phần mềm thuê để phát triển một phiên bản máy tính cho trò chơi này, và bạn được chọn để xây dựng một trong các luật đặc biệt của trò chơi.

Khi trò chơi kết thúc, người chơi mà xây dựng được con đường dài nhất sẽ được thêm 2 điểm thắng cuộc.

Vấn đề gặp phải ở đây là người chơi thường xây dựng các mạng lưới con đường rất phức tạp và không chỉ theo một đường tuyến tính. Vì lý do đó, việc xác định con đường dài nhất không phải đơn giản (mặc dù những người chơi thường có thể thấy ngay lập tức).

Đối chiếu tới trò chơi gốc, chúng ta sẽ giải quyết một vấn đề đơn giản ở đây: Bạn được cho trước một tập các nodes (thành phố) và một tập các cạnh (các đoạn đường) có chiều dài là 1 kết nối các nodes.

Con đường dài nhất được định nghĩa như là đường đi dài nhất trong mạng lưới đường mà không có cạnh nào được dử dụng hai lần. Dù vậy, các nodes có thể được thăm hơn một lần.

Ví dụ: Mạng lưới sau đây chứa một con đường dài nhất là 12.

Input

Input sẽ chứa một hoặc nhiều test cases.

Dòng đầu là số lượng test case T.

Dòng đầu tiên của mỗi test cases chứa 2 số nguyên: số nodes N (2<=N<=25) và số cạnh M (1<=M<=25). M dòng tiếp theo miêu tả M cạnh. Mỗi cạnh được cho bởi các số node kết nối với nhau. Các node được đánh số từ 0 -> N-1. Các cạnh không có hướng. Các node có bậc là 3 hoặc nhỏ hơn. Mạng lưới không cần thiết phải được kết nối thông suốt với nhau.

Output

Với mỗi test case, in ra chiều dài của con đường dài nhất trên một dòng.

Sample

Input

3

15 16

0 2

1 2

2 3

3 4

3 5

4 6

5 7

6 8

7 8

7 9

8 10

9 11

10 12

11 12

10 13

12 14

3 2

0 1

1 2

15 16

0 2

1 2

2 3

3 4

3 5

4 6

5 7

6 8

7 8

7 9

8 10

9 11

10 12

11 12

10 13

12 14

Output

12

2

12

Pizza Location

Our friend Picko is very reach and he wants to open lots of restaurants with delivery. The main food will be, of course, pizza. He has certain number of potential locations for the restaurants, and he knows the locations of the solitaires with lots of people which will often be his customers. Delivery of each restaurant will cover all the solitaires in given radius.

Picko can open only limited number of restaurants, and he wants that restaurants on the locations which will cover maximal number of people in solitaires.

Write a program that will calculate maximal number of people which we can cover with delivery.

Input

In the first line of the input file there are two integers K and R, separated with space, number of restaurants and radius of delivery, 1 ≤ K ≤ 10, 1 ≤ R ≤ 500.

In the second line there is integer M, number of locations, K ≤ M ≤ 20.

In each of the next M lines there are two integer X and Y, separated with space, coordinates of each location, -1000 ≤ X,Y ≤ 1000.

In the next line there is integer N, number of solitaires, 1 ≤ N ≤ 100.

In each of the next N lines there are three integers X, Y and S, separated with space, X and Y are coordinates of each solitaire, and S is number of people in that solitaire, -1000 ≤ X,Y ≤ 1000, 1 ≤ S ≤ 100.

We consider that solitaire is in radius of some restaurant if distance between them is less or equal to R. There are no two locations of restaurants on the same place.

Output

In only line of the output file we have to write maximal number from the text above.

Sample

Input

3

2 2

3

1 0

4 0

7 0

4

0 0 1

3 0 7

5 0 9

8 0 1

2 2

3

-2 0

0 1

3 0

8

-3 1 1

-3 0 1

-3 -1 1

-2 -1 1

0 0 3

0 2 1

2 1 3

4 0 2

3 3

5

0 0

1 6

2 3

6 6

7 2

8

0 1 2

0 5 3

0 6 1

1 0 1

3 2 3

3 6 2

6 2 4

8 6 3

Output

#1 18

#2 12

#3 17

Picking up Jewels

There is a maze that has one entrance and one exit.
Jewels are placed in passages of the maze.
You want to pick up the jewels after getting into the maze through the entrance and before getting out of it through the exit.
You want to get as many jewels as possible, but you don’t want to take the same passage you used once.

When locations of a maze and jewels are given,
find out the greatest number of jewels you can get without taking the same passage twice, and the path taken in this case.

Time limit : 1 sec (Java : 2 sec)

[Input]
There can be more than one test case in the input file. The first line has T, the number of test cases.
Then the totally T test cases are provided in the following lines (T ≤ 10 )

In each test case,
In the first line, the size of the maze N (1 ≤ N ≤ 10) is given. The maze is N×N square-shaped.
From the second line through N lines, information of the maze is given.
“0” means a passage, “1” means a wall, and “2” means a location of a jewel.
The entrance is located on the upper-most left passage and the exit is located on the lower-most right passage.
There is no case where the path from the entrance to the exit doesn’t exist.

[Output]

Output the greatest number of jewels that can be picked up.

[I/O Example]

Input
2
5
0 0 0 2 0
2 1 0 1 2
0 0 2 2 0
0 1 0 1 2
2 0 0 0 0
6
0 1 2 1 0 0
0 1 0 0 0 1
0 1 2 1 2 1
0 2 0 1 0 2
0 1 0 1 0 1
2 0 2 1 0 0

Output

6
4

input:

10
6
0 2 0 1 2 0
1 1 0 1 0 1
0 0 2 0 0 2
0 1 1 1 1 2
0 2 0 0 2 2
1 1 1 1 2 2
5
0 0 0 2 0
2 1 0 1 2
0 0 2 2 0
0 1 0 1 2
2 0 0 0 0
10
0 1 0 2 0 0 0 2 0 2
0 0 0 1 1 0 1 0 1 2
2 1 2 1 1 0 1 0 1 0
0 1 2 1 1 0 1 0 1 2
0 0 2 0 0 2 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 0 1 2 1 2 2 1 2
2 1 0 1 0 1 0 2 0 0
0 1 0 1 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 0
7
0 0 0 2 0 0 0
0 1 1 0 1 1 0
2 1 1 0 1 1 0
0 0 0 2 0 2 2
0 1 1 2 1 1 0
0 1 1 0 1 1 0
2 0 0 2 2 1 0
6
0 2 0 1 2 0
2 1 0 1 0 1
2 2 2 0 0 2
0 1 1 0 1 2
0 2 0 0 2 2
1 1 1 1 2 2
10
0 1 2 2 2 0 2 1 1 0
0 1 0 1 1 1 0 2 2 0
0 2 0 2 0 0 0 1 1 0
2 1 0 1 0 1 0 1 2 0
0 1 1 1 0 1 2 1 1 0
2 1 0 1 0 1 0 1 1 0
0 0 0 0 0 1 0 2 2 0
0 1 0 1 1 1 0 1 2 2
2 1 0 1 1 1 0 1 1 0
0 0 2 0 0 0 0 2 2 0
10
0 0 0 2 0 0 1 0 2 0
0 1 0 1 0 1 1 2 1 0
2 1 0 1 2 1 1 0 1 0
0 0 0 2 0 0 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 2 1 0 1 2 2 1 0
0 1 0 2 0 0 2 1 2 0
0 1 0 1 0 1 2 1 2 0
0 1 0 1 0 1 2 1 1 0
0 0 0 0 0 0 2 1 1 0
10
0 1 0 2 0 0 0 2 0 2
0 0 0 1 1 0 1 0 1 2
2 1 2 1 1 0 1 0 1 0
0 1 2 1 1 0 1 0 1 2
0 0 2 0 0 2 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 0 1 2 1 2 2 1 2
2 1 0 1 0 1 0 2 0 0
0 1 0 1 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 0
10
0 0 0 2 0 0 1 0 2 0
0 1 0 1 0 1 1 2 1 0
2 1 0 1 2 1 1 0 1 0
0 0 0 2 0 0 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 2 1 0 1 2 2 1 0
0 1 0 2 0 0 2 1 2 0
0 1 0 1 0 1 2 1 2 0
0 1 0 1 0 1 2 1 1 0
0 0 0 0 0 0 2 1 1 0
10
0 1 0 2 0 0 0 2 0 2
0 0 0 1 1 0 1 0 1 2
2 1 2 1 1 0 1 0 1 0
0 1 2 1 1 0 1 0 1 2
0 0 2 0 0 2 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 0 1 2 1 2 2 1 2
2 1 0 1 0 1 0 2 0 0
0 1 0 1 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 0

output:
8
6
17
7
11
17
15
17
15
17

Bảo vệ nông trang

Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này.

Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm N (1 < N <= 700) hàng và M (1 < M <= 700) cột. Mỗi phần tử của ma trận là độ cao H_ij so với mặt nước biển (0 <= H_ij <= 10,000) của ô (i, j). Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là 1 hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ X không quá 1 và chênh lệch tọa độ Y không quá 1.

[Input]

* Dòng 1: Số lượng mẫu

* Dòng 2: Hai số nguyên cách nhau bởi dấu cách: N và M

* Dòng 3: N+1: Dòng i+1 mô tả hàng i của ma trận với M số nguyên cách nhau bởi dấu cách: H_ij

[Output]

* Dòng 1: Một số nguyên duy nhất là số lượng đỉnh đồi.

[Sample]

[Input]

3

8 7

4 3 2 2 1 0 1

3 3 3 2 1 0 1

2 2 2 2 1 0 0

2 1 1 1 1 0 0

1 1 0 0 0 1 0

0 0 0 1 1 1 0

0 1 2 2 1 1 0

0 1 1 1 2 1 0

8 7

4 3 2 2 1 1 1

3 3 3 2 1 0 1

2 2 2 2 1 0 0

2 1 1 1 1 0 0

1 1 0 0 0 1 0

0 0 0 1 1 1 0

0 1 2 2 1 1 0

0 1 1 1 2 1 0

8 7

4 3 2 2 1 1 1

3 3 3 2 1 0 1

2 2 2 2 1 0 0

2 1 1 2 1 0 0

1 1 2 2 0 1 0

0 0 0 2 1 1 0

0 1 2 2 1 1 0

0 1 1 1 2 1 0

[Output]

#1 3

#2 2

#3 1

Uniform Distribution in Square

An uniform distribution of an n xn square array of cells is a partition of the n*n cells in the array inexactly n sets, each one with n contiguous cells. Two cells are contiguous when they have a common side.

12.PNG

A good uniform distribution is composed of contiguous regions. The figures show a good and a wrong uniform distribution for a 5 x 5 square:
Note that in the second example the cells labeled with 4 describe three non-contiguous regions and cells labeled with 5describe two non-contiguous regions. You must write a program that evaluates if an uniform distribution of the cells in a square array is good or not.

Input

The first line contains the number of test cases.  Test cases follow in next lines.

It is understood that a cell in an n x n square array is denoted by a pair (i, j),with 1 <= i  , j<= n. The input file contains several test cases. Each test case begins with a line indicating n, 0100,the side of the square array to be partitioned. Next, there are n-1 lines, each one corresponding to one partition of the cells of the square, with some non-negative integer numbers. Consecutive integers in a line are separated with a single blank character. A line of the form

a1 a2 a3 a4…

means that cells denoted with the pairs (a1,a2),(a3, a4), … belong to one of the areas in the partition.

The last area in the partition is defined by those cells not mentioned in the n- 1 given lines.

Output

For each test case ‘good’ must be printed if the uniform distribution is good, in other case, ‘wrong’ must be

printed. The answers for the different cases must preserve the order of the input.  The first output line for each test case should be “Case #tn”, where tn is the test case number.

Sample

Input

3

2

1 2 2 1

5

1 1 1 2 1 3 3 2 2 2

2 1 4 2 4 1 5 1 3 1

4 5 5 2 5 3 5 5 5 4

2 5 3 4 3 5 4 3 4 4

5

1 1 1 2 1 3 3 2 2 2

2 1 3 1 4 1 5 1 4 2

4 5 5 2 5 3 5 5 5 4

2 4 1 4 3 5 4 3 4 4

Output

Case #1

wrong

Case #2

good

Case #3

wrong

Biểu thức Zero

Cho một số tự nhiên N ≤ 9. Giữa các số từ 1 đến N hãy thêm vào các dấu + và – sao cho kết quả thu được bằng 0. Hãy viết chương trình tìm tất cả các khả năng có thể.

[Input]

Dòng đầu tiên là T số testcase. T dòng tiếp theo là các số tự nhiên N <= 9.

[Output]

Mỗi test case in ra “# ” theo sau là số lượng kết quả tìm được mỗi test case.

[Sample]

[Input]

1

7

[Output]

#1 6

Giải thích

1-2-3-4-5+6+7=0

1-2+3+4-5+6-7=0

1-23-45+67=0

1-23+4+5+6+7=0

1+2-3-4+5+6-7=0

1+2-3+4-5-6+7=0

Crazy King

King Peter lives in kingdom A, and his daughter in kingdom B. King received a letter telling that her daughter gave birth to a child. King is incredibly curious to see his grandchild! Unfortunately that’s not gonna be that easy.
Kingdoms A and B are separated by a forest. There are lots of enemies in the forest, and King is not that curious to see them. If they attack king on his way to kingdom B, then he will never ever see his grandchild and daughter again because of lethal consequences.

Security Council of the King disposes information about location of the enemies, which makes the things easier for king. For some unknown reason a forest is MxN chessboard. (N is the number of rows, and M is the number of columns). N,M <=100 are positive integers.

Enemies of the King can ride horses as showed in the picture. Usually horses ride (or jump) that way in Chess. Unfortunately king can’t take an airplane from point A to point B because it is not invented yet. So he moves the same way as chess-king does (refer to picture for details).
King can’t move to a square X, if a horse of the enemy is on that square. While the king is moving horses are not, but if at least one horse can reach square X in one move, then king can’t move to that square (except for the case when square X is either kingdom A or B).

You are the chief of Electronic Intelligence department of kingdom A (by the way the computers are already invented). And you’re asked to find the length of the shortest route L from kingdom A to

B, as king can’t wait any longer.

Input

The first line of input contains the number of tests T <=100. The first line of each test contains 2 numbers M and N. Then M lines follow each containing N symbols from the set S = { ‘.’, ‘Z’, ‘A’, ‘B’}. ‘.’ means that square is not occupied. ‘Z’ – horse occupies that square. ‘A’ – kingdom A, ‘B’ – kingdom B. Each test contains exactly one kingdom A and B.

Output

Find number L for each test and print line L if King can reach kingdom B. Replace L with corresponding number. If King can’t safely reach the kingdom B print line -1.

Sample

Input

4

5 5

.Z..B

..Z..

Z…Z

.Z…

A….

3 2

ZB

.Z

AZ

6 5

….B

…..

…..

..Z..

…..

A..Z.

3 3

ZZ.

AB.

Output

-1

2

-1

1