Nitori Kawashiro cần thiết kế hệ thống cáp treo 2 chiều giữa ~n~ địa điểm. Biết rằng nếu có đường đi giữa địa điểm ~a~ tới địa điểm ~b~ và từ địa điểm ~b~ tới địa điểm ~c~ thì có thể đi từ ~a~ đến ~c~. Hãy cho biết cần xây dựng ít nhất bao nhiêu đường đi trực tiếp giữa 2 địa điểm để kết nối ~m~ cặp địa điểm cho trước.

Nói tóm lại, từ đồ thị được cho ban đầu, hãy tìm cách giữ lại ít cạnh nhất sao cho số vùng liên thông được giữ nguyên.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m \le 10^5~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 địa điểm ~u, v \le n~.

Output

• In ra một số ~p~ là số lượng đường đi trực tiếp giữa 2 địa điểm.
• ~p~ dòng sau mỗi dòng in ra 2 số ~u, v~ nghĩa là xây đường đi giữa 2 địa điểm ~u~ và ~v~.

Sample Test

Input:

4 2
1 2
1 4

Output:

2
1 2
2 4

Đất nước ~ABC~ gồm ~n~ thành phố nối với nhau bởi ~m~ con đường. Con đường thứ ~i~ nối hai chiều giữa hai thành phố ~u_i~ và ~v_i~, với độ dài là ~1~.

Luật pháp của ~ABC~ rất lạ, có ~k~ bộ ba được coi là "xấu" ~(a_i,b_i,c_i)~, khi di chuyển, bạn không được đi liên tiếp qua các thành phố ~a_i,b_i,c_i~. Lưu ý rằng, vẫn có thể đi theo thứ tự liên tiếp ~a_i,c_i,b_i~.

Bạn cần đi từ thành phố ~1~ tới ~n~, hãy tìm cách di chuyển ngắn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,m,k~ ~(n \le 3000; 1 \le m \le 2 \times 10^4; 0 \le k \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~u_i, v_i~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i)~.
• ~k~ dòng sau, mỗi dòng gồm ba số nguyên dương ~a_i,b_i,c_i~ ~(1 ≤ a_i, b_i, c_i ≤ n) ~

Output

• Dòng đầu chứa một số ~d~ là đường đi ngắn nhất, nếu không có hãy in ra ~-1~.

Subtask

• Subtask ~2~: Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

2

Hai con thiên nga đang ở trong một cái hồ lớn, nhưng chúng lại đang bị chia cắt bởi băng đóng trong hồ nước. Hồ nước có dạng hình chữ nhật được chia thành ~r~ dòng ~c~ cột. Một số ô trong hồ bị băng đóng. Mùa xuân tới dần, băng trong hồ tan dần – mỗi ngày băng ở tất cả những ô tiếp xúc với nước đang ấm dần trong hồ (tức là kề cạnh một ô không bị đóng băng) sẽ tan ra.

Thiên nga có thể di chuyển tự do ở những ô chứa nước nhưng không thể đi qua những ô bị đóng băng. Bạn hãy tính xem sau bao nhiêu ngày thì đôi thiên nga của chúng ta có thể gặp nhau

Input

• Dòng đầu tiên chứa 2 số ~r~ và ~c~, ~1 \le r, c \le 1500~.
• Mỗi dòng trong ~r~ dòng tiếp theo chứa ~c~ kí tự mô tả hồ nước tại thời điểm hiện tại: '.' (dot) thể hiện 1 ô chứa nước, 'X' thể hiện 1 ô bị đóng băng, và 'L' thể hiện ô có thiên nga. Có chính xác 2 ô chữ L.

Output

• Một dòng duy nhất chứa số ngày đôi thiên nga có thể gặp nhau.

Example

Input

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

Output

3

Trung và FireGhost đã bị phù thủy xấu xa Lihwy nhốt vào mê cung!

Mê cung là một đồ thị gồm ~n~ phòng, các phòng được nối với nhau bởi các mật đạo; biết giữa hai căn phòng chỉ có tối đa một mật đạo, và không tồn tại mật đạo nối một căn phòng với chính nó. Hiện tại, Trung và FireGhost đang ở phòng ~1~, và để thoát ra ngoài, họ cần phải đi đến phòng ~n~. Tuy nhiên, mỗi căn phòng đều có một con quái vật đáng sợ đang chờ họ sẵn, biết con quái vật trong phòng thứ ~i~ có sức mạnh ~a_i~.

Giữa lúc đang đau khổ, thần đèn Alànhddin xuất hiện và ban cho Trung và FireGhost một thanh kiếm với sức mạnh tuỳ ý để đánh bại đám quái vật! Nếu 2 người chọn thanh kiếm có sức mạnh ~x~, họ có thể đánh bại toàn bộ quái vật có sức mạnh không vượt quá ~x~; ngược lại, họ sẽ bị con quái vật đó nuốt chửng.

Tuy nhiên, Alànhddin là một kẻ tư bản: nếu Trung và FireGhost sử dụng thanh kiếm có sức mạnh là ~x~ và số quái vật mà Trung và FireGhost cần phải tiêu diệt ít nhất để đến căn phòng ~n~ là ~y~, họ sẽ phải trả cho Alànhddin số tiền là ~|x - y|~. Hãy giúp Trung và FireGhost chọn thanh kiếm có sức mạnh phù hợp để số tiền phải trả là ít nhất có thể nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~n~ và ~m~ (~1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5~) — lần lượt là số phòng và số mật đạo trong mê cung.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~) — sức mạnh của con quái vật trong căn phòng thứ ~i~.

~m~ dòng tiếp theo, dòng thứ ~j~ gồm ~2~ số nguyên dương ~u_j, v_j~ (~1 \le u_j, v_j \le n~) thể hiện một mật đạo nối ~2~ căn phòng ~u_j~ và ~v_j~.

Output

Một số nguyên duy nhất là đáp án của bài toán: số tiền ít nhất mà Trung và FireGhost phải trả. Nếu Trung và FireGhost không thể đến được căn phòng ~n~, in ra đáp án ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

1

Sample Input 2

2 0
1 2

Sample Output 2

-1

Notes

Trong test ví dụ thứ nhất, khi đi từ ~1~ đến ~4~, bạn phải lần lượt đánh bại ~3~ con quái vật có sức mạnh ~1~, ~4~, ~2~. Nếu thanh kiếm có sức mạnh là ~4~, Trung và FireGhost sẽ có thể đến được căn phòng ~4~ với chi phí là ~|4-3| = 1~. Vậy đáp án là ~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

Cho một đồ thị vô hướng gồm ~n~ đỉnh ~m~ cạnh. Cạnh ~i~ nối giữa đỉnh ~u_i~ và ~v_i~ và có kí tự ~c_i~ được viết lên trên nó.

Hãy tìm một đường đi từ ~1~ đến ~n~ ngắn nhất mà sau khi viết các kí tự có được khi đi qua các cạnh là một xâu palindrome. Nếu không tồn tại bất kì đường đi nào thỏa mãn là palindrome, in ra ~-1~.

Lưu ý: Đồ thị có thể tồn tại khuyên và cạnh lặp, các đỉnh và cạnh có thể đi qua lại nhiều lần.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 1000)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~u_i, v_i, c_i~ mô tả cạnh thứ ~i~ của đồ thị.

Output

• Nếu tồn tại một đường đi tạo ra xâu palindrome, in ra độ dài ngắn nhất có thể. Nếu không, in ra ~-1~.

Sample Input 1

4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a

Sample Output 1

5

Explanation 1

Đi qua các cạnh ~2, 3, 4, 5, 5~, ta nhận được xâu aabaa.

Sample Input 2

3 4
1 1 a
1 2 a
2 3 b
3 3 b

Sample Output 2

-1