Untitled

Bai 1: Mario
Mario Climb

 

0

0

1

3

1

1

1

0

0

0

0

0

2

1

1

1

 

Mario cần phải di chuyển từ vị trí có giá trị bằng 2 và ăn vàng ở ô có giá trị bằng 3

0 là nhữngô Mario không thể qua

1 là nhữngô Mario có thể qua

2 là vị trícủa Mario

3 là vị trí Mario cần di chuyển đến

Các vị trí này được thể hiện bằng ma trận NxM( 2<=N,M<=50)

Mario có thểdi chuyển theo hàng ngang hoặc hàng dọc

Hàng ngang mario chỉ nhảy được tối đa 1 bước

Hàng dọc mario có thể nhảy được “h” bước

Tìm bước nhảy “h” tối thiểu để Mario có thể ăn được vàng

Sample Input

3

5 8

1 1 1 1 0 0 0 0

0 0 0 3 0 1 1 1

1 1 1 0 0 1 0 0

0 0 0 0 0 0 1 0

2 1 1 1 1 1 1 1

5 6

0 1 1 1 0 0

3 1 0 1 1 0

0 0 0 0 1 1

0 0 0 0 0 1

2 1 1 1 1 1

9 13

0 1 1 1 1 1 1 1 1 1 1 1 1

1 1 0 0 0 0 0 0 0 0 0 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 1 3

0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0

2 1 1 1 1 1 1 1 1 1 1 1 1

Sample output

Case #1

2

Case #2

1

Case #3

3
Bai 2: 
Pink and Blue
Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy.

Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition:

Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa.

Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion.

So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize "inversions". Help him solve the task.

Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation.

 

Input
The first line is the number of test cases T.

First line of each test case contains 2 space-separated integers - N and M - number of students and number of friendships present respectively.

Second line consists of N space-separated characters, where ith character denotes the gender of the ith student. B: Boy, G: Girl.

M lines follow. Each line consists of 2 space-separated integers, u and v, showing that u is a friend of v and vice-versa.

 

Output
If Xenny could distribute the T-Shirts in the desired way, print the minimum number of inversions required.
Else, print -1.

 

Constraints
1 ≤ N ≤ 105
1 ≤ M ≤ 105
1 ≤ u, v ≤ N

Colors of T-Shirt are represented by uppercase characters 'B' and 'G'

 

Sample

 

Input

3

3 2

B G B

1 2

1 3

6 9

B B B G G G

3 5

2 6

4 2

6 3

3 1

3 4

6 1

5 1

1 4

6 5

G G G B G G

6 3

1 3

2 3

4 3

5 3

 

Output 

1

-1

2

 

Explanation

#1

Student 1 can be given a Blue T-Shirt. Hence, Student 2 and 3 would receive Pink T-Shirts. Since, Student 3 is a Boy and has received a Pink T-Shirt, number of inversions = 1.
Bai 3: Mountain Walking
Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.

 

Input

Dòng 1: Số test case

Dòng 2: N

N dòng tiếp theo chứa N số nguyên, mỗi số cho biết cao độ của một ô.

 

Output

In ra #test case và một số nguyên là chênh lệch độ cao nhỏ nhất.

 

Sample

 

Input

5

5

1 1 3 6 8

1 2 2 5 5

4 4 0 3 3

8 0 2 3 4

4 3 0 2 1

5

99 85 38 22 55

89 28 33 3 65

99 20 14 67 90

36 27 28 77 31

50 45 12 9 14

2

92 83

19 91

5

61 49 32 34 28

100 65 0 10 89

34 99 40 86 4

10 97 49 21 30

95 33 79 51 65

2

17 60

94 27

 

Output

#1 2

#2 85

#3 9

#4 50

#5 43
Bai 4: uần Trăng Mật
Tuần trăng mật

Đám cưới anh Uranus diễn ra rất vui vẻ, chỉ có Tomoky là có chút hậm hực. Sau đám cưới, anh Uranus muốn đi tuần trăng mật ở thành phố Đà Lạt xinh đẹp.

Thành phố Đà Lạt gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m (m <= n*(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1,2,…m) cho phép đi từ địa điểm u_j tới địa điểm v_j với chi phí đi lại là số nguyên dương c(u_j, v_j).

Anh Uranus muốn xuất phát từ điểm du lịch 1 và đi thăm k địa điểm du lịch s_1, s_2, …, s_k (khác địa điểm 1) và sau đó quay về địa điểm xuất phát 1 với tổng chi phí là nhỏ nhất.

Cho thông tin về hệ thống giao thông và k địa điểm du lịch s_1, s_2, …, s_k. Hãy giúp anh Uranus xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm s_1, s_2, …, s_k sau đó quay về địa điểm du lịch 1 với tổng chi phí nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên dương T là số bộ test. Mỗi bộ test gồm:

• Dòng thứ nhất chứa 3 số nguyên n, m, k (n <= 1000 và k <= 15).

• Dòng thứ hai chứa k số nguyên dương s_1, s_2, …, s_k.

• Dòng thứ j trong m dòng tiếp theo chứa 3 số nguyên dương u_j, v_j, c(u_j, v_j) cho biết thông tiên về tuyến đường thứ j. Biết rằng u_j luôn khác v_j, và c(u_j, v_j) <= 10^9.

Output

In ra một số nguyên là tổng chi phí nhỏ nhất tìm được. Nếu không tìm được một hành trình du lịch nào, in ra số -1.

Example

Input:

1

6 8 2

2 5

1 2 4

2 4 2

4 3 3

3 1 4

4 1 5

3 5 5

5 3 1

5 6 7

 Output:

Case #1

19



Case #2

57