Cho một đồ thị có hướng không trọng số gồm ~n~ đỉnh và ~m~ cạnh. Bạn đang đứng ở đỉnh ~S~ của đồ thị và mục tiêu của bạn là đến được đỉnh ~T~. Tuy nhiên, khác với bình thường, mỗi bước đi của bạn chỉ có thể đi qua đúng ~3~ cạnh nối tiếp nhau bắt đầu từ đỉnh đang đứng. Ví dụ, có bốn cạnh ~(1,2), (2,3), (3,4), (3,5)~, khi đứng ở đỉnh ~1~ thì trong một bước bạn chỉ được đi tới đỉnh ~4~ hoặc ~5~.

Cho đỉnh ~S~ và ~T~ hãy tìm số bước đi ngắn nhất để từ đỉnh ~S~ tới được ~T~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả số đỉnh và số cạnh.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ miêu tả cạnh một chiều ~u,v~.
• Dòng cuối gồm ~2~ số nguyên dương ~S~ và ~T~ miêu tả đỉnh xuất phát và đỉnh đích.

Output

• In ra một số là số bước ít nhất để đi từ ~S~ tới ~T~, nếu không có cách đi nào thì in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 2*10^5~

Ví dụ

Input 1:

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

Output 1:

2

Input 2:

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

Output 2:

-1

Cho một đơn đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Độ dài của mỗi cạnh là ~1~. Ta định nghĩa khoảng cách giữa hai đỉnh ~u~ và ~v~ là độ đường đi ngắn nhất từ ~u~ đến ~v~.

Ban đầu, tất cả các đỉnh được tô màu ~0~. Cho ~q~ truy vấn, truy vấn thứ ~i~ yêu cầu tô màu ~c_i~ cho tất cả các đỉnh có khoảng cách đến ~u_i~ nhỏ hơn hoặc bằng ~d _i~.

Hãy cho biết màu của từng đỉnh sau khi thực hiện xong ~q~ truy vấn trên.

Input

• Dòng đầu ghi hai số nguyên dương ~n,m~ miêu tả số cạnh và số đỉnh.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_i~ và ~v_i~ ~(u_i, v_i \le n)~ mô tả một cạnh trong đồ thị. Dữ liệu vào đảm bảo đồ thị đã cho là đơn đồ thị.
• Dòng tiếp theo ghi số nguyên dương ~q~ - miêu tả số truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng ghi ba số nguyên ~u_i, d_i, c_i~

Giới hạn

• ~n,m,q \le 10^5~.
• ~d_i \le 10~.
• ~c_i \le 10^5~.

Output

In ra ~n~ dòng, dòng thứ ~i~ in ra một số nguyên duy nhất - màu của đỉnh ~i~ sau khi thực hiện ~q~ truy vấn trên.

Sample Input

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

Sample Output

0
1
1
2
3
2
1

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

Mikoto đang ở trong một mê cung được biểu diễn bởi một bảng vuông gồm ~N~ hàng và ~N~ cột. Mỗi ô hoặc là ô trống, hoặc là ô bị chặn.

Ô nằm ở hàng ~i~, cột ~j~ được ký hiệu là ~(i, j)~ với ~1 <= i, j <= N~.

Ban đầu, Mikoto đứng tại ô ~(sx, sy)~ và muốn đi tới ô đích ~(gx, gy)~. Hai ô này luôn là ô trống.

Mikoto có thể thực hiện các thao tác sau, theo thứ tự bất kỳ, không giới hạn số lần:

• Bắn railgun theo hàng hiện tại: toàn bộ các ô trong hàng đang đứng sẽ trở thành ô trống. Thao tác này tốn ~A~ đơn vị thời gian.
• Bắn railgun theo cột hiện tại: toàn bộ các ô trong cột đang đứng sẽ trở thành ô trống. Thao tác này tốn ~A~ đơn vị thời gian.
• Đi bộ sang một ô kề cạnh đang trống: từ ~(x, y)~ có thể sang một trong bốn ô ~(x - 1, y)~, ~(x + 1, y)~, ~(x, y - 1)~, ~(x, y + 1)~ nếu ô đó nằm trong bảng. Thao tác này tốn ~B~ đơn vị thời gian.

Lưu ý rằng sau khi một hàng hoặc một cột bị bắn railgun, mọi ô trên hàng hoặc cột đó sẽ được xem là ô trống cho các bước di chuyển tiếp theo.

Do thể trạng mỗi ngày khác nhau, Mikoto muốn xét ~Q~ kịch bản. Ở kịch bản thứ ~i~, chi phí bắn railgun và đi bộ lần lượt là ~(ai, bi)~.

Với mỗi kịch bản, hãy tính thời gian nhỏ nhất để Mikoto đi từ ~(sx, sy)~ tới ~(gx, gy)~.

Input

• Dòng đầu chứa số nguyên ~N~.
• Dòng thứ hai chứa ~4~ số nguyên ~sx~, ~sy~, ~gx~, ~gy~.
• ~N~ dòng tiếp theo, mỗi dòng là một xâu độ dài ~N~ chỉ gồm:
  • ~.~: ô trống
  • ~\#~: ô bị chặn
• Dòng tiếp theo chứa số nguyên ~Q~.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~ai~, ~bi~.

Output

• In ra ~Q~ dòng.
• Dòng thứ ~i~ là đáp án cho kịch bản thứ ~i~: thời gian nhỏ nhất để đi từ ô xuất phát tới ô đích.

Subtask

• Subtask 1: ~N <= 300~ ~(50\%)~
• Subtask 2: Không có ràng buộc gì thêm ~(50%)~

Ràng buộc

• ~1 <= N <= 1000~
• ~1 <= sx, sy, gx, gy <= N~
• ~(sx, sy)~ và ~(gx, gy)~ ban đầu là ô trống
• ~1 <= Q <= 10^6~
• ~1 <= ai, bi <= 10^9~

Sample Input

4
1 1 4 1
....
###.
###.
....
3
13 213883
1315 3281
1 1

Sample Output

641662
11158
4

Cho ~A~ là ~1~ ma trận vuông có kích thước ~n \times n~ và ~A~ chỉ gồm các ô có giá trị ~0~ hoặc ~1~. Tìm số nguyên dương ~k~ nhỏ nhất sao cho lũy thừa bậc ~k~ của ma trận ~A~ là ma trận gồm toàn các số ~0~, biết rằng lũy thừa của một ma trận được mô tả như sau:

Input:

• Dòng đầu gồm ~2~ số nguyên ~n~ và ~m~ trong đó ~n~ là kích thước ma trận còn ~m~ là số ô có giá trị bằng ~1~ trên ma trận ~A~.
• ~m~ dòng tiếp theo, trên mỗi dòng có một cặp số ~(i, j)~ ~(1 \leq i, j \leq n)~ là tọa độ của các ô có giá trị bằng ~1~ trên ma trận ~A~, dữ liệu đảm bảo rằng không có cặp số ~(i, j)~ nào xuất hiện ~2~ lần. Một ô có tọa độ ~(i, j)~ nếu như nó nằm tại dòng thứ ~i~ tính từ trên xuống và cột thứ ~j~ tính từ bên trái sang của ma trận ~A~, nếu toạ độ của ô không nằm trong ~m~ cặp số được cho thì ô đó mặc định có giá trị bằng ~0~.

Constraints

• ~1 \leq n \leq 5 \times 10^5~
• ~0 \leq m \leq 5 \times 10^5~

Subtask

• ~10\%~ số test có ~1 \le n \le 4~.
• ~30\%~ số test khác có ~1 \le n \le 60~.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Output:

• In ra số nguyên dương ~k~ nhỏ nhất hoặc ~-1~ nếu ~k~ không tồn tại.

Sample Input 1:

4 2
1 2
4 3

Sample Output 1:

2

Sample Input 2:

3 3
1 1
2 2
3 3

Sample Output 2:

-1

Explanation

• Ở Sample test 1, dễ thấy ~A^2~ là ma trận toàn ~0~.

• Ở Sample test 2, ma trận ~A~ đã cho được gọi là một Identity matrix, khi lấy lũy thừa bậc ~k~ của một Identity matrix thì giá trị các ô trên ma trận hoàn toàn giữ nguyên.

Tìm đường đi ngắn nhất trong đồ thị không trọng số là bài toán cơ bản mà hầu hết sinh viên khoa học máy tính đều học trong lớp giải thuật đầu tiên.

Tuy nhiên, đây là một biến thể khó hơn: cho một đồ thị có hướng không trọng số với các cạnh có độ dài ~1~, hãy tìm đường đi ngắn nhất chia hết cho ~K~ từ đỉnh nguồn ~0~ đến tất cả các đỉnh còn lại!

Lưu ý rằng cạnh lặp có thể xuất hiện.

Lưu ý rằng đường đi có thể đi qua cùng một đỉnh hoặc cạnh nhiều lần.

Input

• Dòng đầu chứa số nguyên ~T~ — số test case.
• Mỗi test case bắt đầu bằng ~3~ số nguyên ~V~, ~E~, ~K~: số đỉnh, số cạnh và giá trị ~K~.
• ~E~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u~, ~v~ mô tả một cạnh có hướng từ ~u~ đến ~v~.
• Các cạnh không bị trùng nhau.
• ~1 \le T \le 10~
• ~1 \le V \le 300~
• ~0 \le E \le V^2~
• ~1 \le K \le 30\,000~

Output

• Với mỗi test case, in ra một dòng chứa ~V~ số nguyên: độ dài đường đi ngắn nhất chia hết cho ~K~ từ đỉnh ~0~ đến từng đỉnh ~i~. Nếu không tồn tại đường đi thỏa mãn, in ~-1~. Số đầu tiên luôn là ~0~.

Sample Input 1

3
3 3 2
0 1
1 2
2 0
4 12 3
0 1
0 2
0 3
1 0
1 2
1 3
2 0
2 1
2 3
3 0
3 1
3 2
4 5 7
0 1
0 3
1 1
2 2
3 3

Sample Output 1

0 4 2
0 3 3 3
0 7 -1 7

Vương quốc ~Ams~ gồm ~n~ thành phố được liên kết với nhau bằng ~m~ con đường hai chiều, đảm bảo rằng mọi cặp thành phố đều có đường đi trực tiếp hoặc gián tiếp tới nhau. Con đường thứ ~i~ kết nối hai thành phố ~u_i,v_i~, và sẽ tốn ~w_i~ lít xăng để đi qua.

Là một người đam mê du lịch, bạn lên kế hoạch cho chuyến đi chơi của mình tới ~Ams~. Bạn xuất phát từ thành phố ~st~ và có dự định đi tới thành phố ~en~ bằng xe của mình. Tất nhiên đi xe thì phải tốt nhiên liệu, và xe của bạn có một bình xăng chứa được tối đa ~t~ lít xăng.

~Ams~ có ~s~ trạm xăng. Trạm xăng thứ ~i~ được phân bố ở thành phố ~p_i~ và có chi phí cho mỗi lít xăng là ~c_i~. Ở mỗi trạm xăng, bạn có thể mua không giới hạn số xăng (tất nhiên xe bạn chỉ mang tối đa được ~t~ lít xăng thôi).

Bạn bắt đầu từ thành phố ~st~ và xe bạn ban đầu không có xăng - may mắn rằng đảm bảo luôn có trạm xăng ở thành phố nơi bạn xuất phát. Hãy tính số tiền ít nhất cần bỏ ra để hoàn thành hành trình từ ~st~ tới ~en~.

Input

• Dòng đầu gồm ~3~ số nguyên dương ~n,m,s~ ~(2 \le n \le 1000; 1 \le m \le 10^4; 1 \le s \le 100)~
• Dòng tiếp theo gồm một số nguyên dương ~t~ ~(1 \le t \le 10^5)~ mô tả sức chứa của bình xăng.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n; 1 \le w_i \le t)~ miêu tả con đường thứ ~i~.
• ~s~ dòng tiếp theo, dòng thứ ~i~ gồm hai só nguyên dương ~p_i,c_i~ ~(1 \le p_i \le n; 1 \le c_i \le 100)~ miêu tả trạm xăng thứ ~i~.
• Dòng cuối cùng gồm hai số nguyên dương ~st,en~ ~(1 \le st, en \le n)~ miêu tả vị trí ban đầu và đích đến của bạn.

Output

• In ra số tiền ít nhất cần để di chuyển.

Subtask

• Subtask ~1~ ~(30\%)~: ~n \le 100; m \le 100; t \le 500~
• Subtask ~2~ ~(30\%)~: ~t \le 500~
• Subtask ~3~ ~(40\%)~: Không giới hạn gì thêm.

Sample Input 1:

3 3 2
200
1 3 80
1 2 50
2 3 50
1 70
2 40
1 3

Sample Output 1:

5500

Sample Input 2:

5 5 3
100
1 2 80
2 5 80
1 3 40
3 4 60
4 5 60
1 8
2 9
3 2
1 5

Sample Output 2:

1340

Sample Input 3:

4 3 3
10
1 2 2
2 3 6
3 4 3
1 4
2 7
3 9
2 4

Sample Output 3:

61