Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Đây là tài liệu mật và khẩn cấp, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) = .~, nếu đây là một ô bình thường có thể đi.
• ~c(i,j) = *~, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) = S~, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) = T~, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả kích thước bảng.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.

Output

• In ra một dòng là khoảng cách đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Nếu không có một đường đi nào như vậy, in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 1000~

Ví dụ

Input 1:

3 4 
S...
....
...T

Output 1:

5

Input 2:

3 4 
S.*T
*.*.
*...

Output 2:

7

Năm ~1976~, "Định lý bản đồ bốn màu" đã được chứng minh với sự hỗ trợ của máy tính. Định lý này cho rằng mọi bản đồ có thể được tô màu chỉ bằng bốn màu, theo cách mà không có vùng nào được tô màu sử dụng cùng màu với vùng lân cận.

Tuy nhiên, ở đây bạn được yêu cầu giải một bài toán tương tự nhưng đơn giản hơn. Bạn cần kiểm tra xem một đồ thị được cho có thể được "tô màu" hay không. Một đồ thị có thể coi là được "tô màu", nếu ta có thể gán một màu (chỉ sử dụng đúng hai màu) cho các nút sao cho không có hai nút liền kề nào có cùng màu.

Đồ thị được cho có một vài điều kiện như sau:

• Không có khuyên.
• Đồ thị vô hướng.
• Đồ thị liên thông.

Input

• Dòng thứ nhất gồm số nguyên dương ~t~ miêu tả số test case.
• Đối với mỗi test case:
  • Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả đỉnh của đồ thị. Lưu ý, các đỉnh trong đồ thị được đánh dấu từ ~0~ tới ~n-1~.
  • Dòng thứ hai gồm số nguyên dương ~m~ miêu tả số cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u,v~ miêu tả cạnh ~(u,v)~.

Output

• Với mỗi test case, in ra "BICOLORABLE." nếu có thể "tô màu" đồ thị, ngược lại in ra "NOT BICOLORABLE.".

Constraints

• ~1 \le t \le 20~
• ~1 \le n,m \le 200~

Sample Input 1:

3

3
3
0 1
1 2
2 0

3
2
0 1
1 2

9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8

Sample Output 1:

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

Đất nước U có ~n~ thành phố, đánh số từ 1 đến ~n~. Các thành phố được nối với nhau bởi hệ thống giao thông gồm m tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp thành phố, đảm bảo luôn có đường đi lại giữa hai thành phố bất kì trong nước (trực tiếp hoặc đi qua một số thành phố khác). Giữa hai thành phố bất kì không có quá một tuyến đường nối trực tiếp.

Có tổng cộng ~b~ kho lương thực được đặt trên khắp cả nước, mỗi kho nằm ở một thành phố khác nhau. Để bảo vệ đất nước khỏi quân xâm lược, Thủ tướng U đã chọn ra ~r~ thành phố khác nhau để đặt trại quân sự.

Yêu cầu: Để giải quyết vấn đề lương thực cho quân doanh, với mỗi thành phố được đặt trại quân sự, nhiệm vụ của bạn là tính toán số tuyến đường ít nhất cần đi nếu xuất phát từ thành phố đó đến một kho lương thực bất kì.

Input

• Dòng thứ nhất gồm bốn số nguyên: ~n,m,b,r\ (2 \le n \le 5.10^5; 1 \le m \le 5.10^5; 1 \le b,r \le n)~
• Dòng thứ hai gồm ~b~ số nguyên là chỉ số của các thành phố được đặt kho lương thực;
• Dòng thứ ba gồm ~r~ số nguyên là chỉ số của các thành phố được đặt trại quân sự;
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~ và ~v~ thể hiện có một tuyến đường hai chiều nối trực tiếp hai thành phố ~u~ và ~v~.

Output

• Xuất ra ~r~ số nguyên trên cùng một dòng là kết quả tính được của các thành phố được đặt trại quân sự theo thứ tự của dữ liệu.

Subtask

• Subtask 1: (40% số test): ~n \le 5000~
• Subtask 2: (60% số test): Không có ràng buộc gì thêm.

Sample Input 1

6 6 2 3
3 2
1 5 4
1 2
1 6
3 6
2 3
4 5
3 4

Sample Output 1

1 2 1

Explanation 1

• Thành phố ~1~: ~1 → 2~
• Thành phố ~4~: ~4 → 3~
• Thành phố ~5~: ~5 → 4 → 3~

Cho đồ thị vô hướng, gồm ~n~ đỉnh và ~m~ cạnh, mỗi đỉnh sẽ có một trọng số.

Hãy tìm một đường đi từ ~1~ tới ~n~ sao cho chênh lệch lớn nhất giữa trọng số của hai đỉnh liền kề trên đường đi là nhỏ nhất có thể.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, 1 \le m \le 2*10^5)~
• ~n~ dòng sau, mỗi dòng gồm ~n~ số nguyên dương ~c_i~ là trọng số của đỉnh thứ ~i~ ~(1 \le c_i \le 10^9)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u_i,v_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i)~ - miêu tả cạnh ~(u_i,v_i)~.

Output:

• In ra chênh lệch lớn nhất giữa trọng số của hai đỉnh liền kề trên đường đi sao cho nó nhỏ nhất có thể.

Constraints:

• Có ~50\%~ số test ứng với ~n \le 2*10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

3 3
1 2 3
1 2
2 3
1 3

Output 1

1

Explanation 1:

Đi đường ~(1,2,3)~ thay vì ~(1,3)~.

Alice vừa mới lạc vào một vùng đất rất kì lạ tên là "Bruhderland". Đây là một vùng đất lai giữa "Wonderland" và "Borderland", nơi có phép màu và cả những trò chơi sinh tử.

Bruhderland được biểu diễn bằng một ma trận ~n \times m~, với ô ~(i,j)~ là một trong các kí tự sau:

• .: có nghĩa là ô đất trống, có thể đi vào.
• *: có nghĩa là ô có một tảng đá, không thể đi vào.
• A: có nghĩa là có một trò chơi với độ khó ~A~ ở ô này, Alice rất giỏi nên sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~1~ sức lực.
• B: có nghĩa là có một trò chơi với độ khó ~B~ ở ô này, Alice vẫn sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~2~ sức lực.

Giả sử, Alice đang ở ô ~(i,j)~, cô có thể đi sang ~4~ ô kề cạnh nếu như ô đó không vượt qua ngoài bảng và không chứa tảng đá nào. Như đã nói, Bruhderland có cả yếu tố phép màu, vậy nên khi vào đây, cô đã học được cách đọc thần chú để phá hủy một tảng đá bất kì mà không mất sức lực nào (nghĩa là có thể đi vào ô chứa tảng đá vừa bị phá hủy), tuy nhiên do năng lực giới hạn, Alice chỉ có thể đọc thần chú ~k~ lần mà thôi.

Alice đang ở ô ~(1,1)~, để thoát ra khỏi Bruhderland, cô sẽ cần đến ô ~(n,m)~. Tuy nhiên, do khá lười tham gia vào các trò chơi, Alice muốn thoát ra khỏi Bruhderland sao cho tốn ít sức lực nhất.

Quan trọng: Dữ liệu đảm bảo kết quả không quá ~2500~.

Input: BRUHDERLAND.INP

• Dòng đầu tiên ghi ~3~ số nguyên dương ~n,m,k~ ~(1 \le n,m \le 1000, 0 \le k \le 5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm một xâu kí tự độ dài ~m~ miêu tả hàng thứ ~i~ của ma trận.
• Dữ liệu đảm bảo ô ~(1,1)~ là kí tự . và luôn tồn tại cách đi từ ~(1,1)~ tới ~(n,m)~ nếu sử dụng thần chú một cách hợp lý.

Output: BRUHDERLAND.OUT

• In ra một số nguyên dương là số sức lực ít nhất cần tiêu tốn để đến được ô ~(n,m)~.

Scoring:

• Subtask ~1~ ~(10\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ chỉ gồm kí tự A
• Subtask ~2~ ~(15\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B và ..
• Subtask ~3~ ~(10\%)~: ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~4~ ~(10\%)~: Các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~5~ ~(15\%)~: ~n \times m \le 10^5~ và ~k = 0~.
• Subtask ~6~ ~(20\%)~: ~n \times m \le 10^5~.
• Subtask ~7~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

4 4 0
.AAA
AAAA
AAAA
AAAA

Sample Output 1

6

Sample Input 2

5 4 0
.AAA
***A
AAAA
A***
AAAA

Sample Output 2

13

Sample Input 3

5 4 0
.AAA
***B
AAAA
A**B
BAAA

Sample Output 3

9

Sample Input 4

5 4 2
.BAA
****
AABA
A***
BABA

Sample Output 4

6