Sau khi Hollywood đã thành công trong câu chuyện về cuộc phiêu lưu trên biển của chiếc ô giữa 2 hòn đảo, Netflix quyết định sẽ thực hiện cho mình chuỗi câu chuyện về cuộc phiêu lưu của 3 chú vịt.

Các bạn chắc hẳn còn nhớ ở vòng đầu tiên của COCI 20/21, những chú vịt có bản đồ dòng biển. Những chú vịt phiêu lưu cùng nhau. Hòn đảo bắt đầu nơi mà những chú vịt sống được kí hiệu bằng kí tự o. Những chú vịt có thể bắt đầu chuyến phiêu lưu nhờ dòng biển. Dòng biển di chuyển theo 1 trong 4 hướng và được chỉ hướng bằng những kí tự: > từ Tây sang Đông, < từ Đông sang Tây, v từ Bắc xuống Nam, ^ từ Nam lên Bắc. Khi những chú vịt ở trong vùng biển này chúng sẽ phải di chuyển theo chiều của dòng biển sang ô khác.

Vùng biển tĩnh lặng được kí hiệu bằng .. Hành trình sẽ kết thúc khi những chú vịt được dòng biển đưa tới nơi biển lặng, ngoài bảng đồ hoặc quay trở về hòn đảo bắt đầu. Hòn đảo đích nơi mà những chú vịt muốn thăm được kí hiệu bởi kí tự x.

Để làm cho chuỗi câu chuyện được thú vị hơn, Netflix đã thay đổi câu chuyện. Vùng biển giờ đây còn có những vòng xoáy (những chú vịt sẽ kẹt trong 1 chu kỳ) và dòng biển có thể đưa những chú vịt ra khỏi bản đồ.

Chính vì vậy, bản đồ gốc đã bị thay đổi. Tuy nhiên với áp lực công việc cao, nhà biên tập đã phạm lỗi khiến cho các chú vịt không thể đi đến hòn đảo đích bằng những dòng biển từ hòn đảo bắt đầu của mình.

Nhà biên tập rất bận rộn. Bạn hãy giúp ông ta khắc phục bằng cách thay đổi ít kí tự nhất trên bản đồ sao cho những chú vịt có thể đi từ hòn đảo bắt đầu đến hòn đảo đích.

Vì lý do cốt truyện nên ô chứa kí tự x hoặc o là không thể thay đổi. Mọi ô còn lại đều thuộc tập kí tự <>^v. và có thể được thay thế bằng các kí tự khác cùng tập kí tự <>^v.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~r~ và ~s~ (~3 \le r, s \le 2000~) lần lượt là số dòng và số cột trên bản đồ.
• ~r~ dòng tiếp theo, mỗi dòng gồm ~s~ kí tự trong tập o<>^v.x mô tả bản đồ của dòng biển.
• Dữ liệu đảm bảo chỉ có một hòn đảo bắt đầu o và một hòn đảo đích x trên bản đồ và chúng không nằm kề nhau.

Output

• Dòng đầu tiên ghi ra số nguyên ~k~ là số kí tự cần đổi.
• ~r~ dòng tiếp theo, mỗi dòng gồm ~s~ kí tự mô tả bản đồ đã được sửa đổi theo yêu cầu.
• Nếu có nhiều bản đồ thỏa mãn, chỉ cần in ra một trong số chúng.

Subtask

Example

Sample Input

3 3
>vo
vv>
x>>

Sample Output

1
>vo
vv>
x<>

Thị trưởng thành phố Aaron vừa qua đã xây dựng mạng lưới các trạm sạc của xe điện Vinfast. Ông đã xác định ~N~ điểm được đánh số từ ~1~ đến ~N~, trong đó ~T~ điểm đầu tiên là các trạm sạc và các điểm còn lại là các khu vui chơi giải trí cao cấp. Các điểm này được kết nối với nhau bởi ~M~ con đường hai chiều, trong đó con đường thứ ~i~ kết nối hai điểm ~u_i~ và ~v_i~ và có chiều dài ~l_i~ dặm.

Một chiếc Vinfast có thể đi tối đa ~R~ dặm trong một lần sạc, từ đó cho phép nó đến bất kỳ điểm đến nào trong phạm vi bán kính ~R~ bắt đầu từ một trạm sạc. Một khu vui chơi được đánh giá là "tốt" nếu nó nằm trong bán kính ~R~ ít nhất của ít nhất ~K~ trạm sạc khác nhau. Nhiệm vụ của bạn là hỗ trợ thị trưởng Aaron trong việc xác định tập hợp các khu vui chơi cao cấp được đánh giá là "tốt".

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ (~1 \le N, M \le 10^5~).
• Dòng thứ hai gồm ba số nguyên dương ~T~, ~R~, ~K~ (~1 \le T < N~, ~1 \le R \le 10^9~, ~1 \le K \le 10~).
• ~M~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~u_i, v_i~ và ~l_i~ (~1 \le u_i, v_i \le n~, ~1 \le l_i \le 10^9~).

Output

• Dòng đầu tiên in ra ~G~ là số khu vui chơi được đánh giá là "tốt".
• ~G~ dòng tiếp theo, mỗi dòng gồm chỉ số ~i~ (~T + 1 \le i \le N~) của khu vui chơi theo thứ tự tăng dần.

Subtask

Example

Sample Input

4 3 2 100 2
1 2 1
2 3 100
1 4 10

Sample Output

1
4

Note

Ta có điểm ~1~ và ~2~ là các trạm sạc.

• ~dis(1, 3) = 101~, ~dis(2, 3) = 100~. Từ đó, khu vui chơi tại điểm ~3~ chỉ nằm trong bán kính ~R = 100~ của duy nhất trạm sạc ~2~.
• ~dis(1, 4) = 10~, ~dis(2, 4) = 11~. Từ đó, khu vui chơi tại điểm ~4~ nằm trong bán kính ~R = 100~ của cả trạm sạc ~1~ và ~2~, vì vậy được đánh đánh giá là "tốt".

Aaron đang có một chuyến đi thăm thành phố ~X~, nơi có ~N~ thị trấn được đánh số từ ~1~ đến ~N~ được kết nối bởi ~M~ con đường một chiều. Đường thứ ~i~ nối từ thị trấn ~a_i~ đến thị trấn ~b_i~ và có được đánh nhãn là ~l_i~.

Một chuyến đi có độ dài ~k~ xuất phát từ thị trấn ~x_0~ là một dãy các thị trấn ~x_0, x_1, \ldots, x_k~, sao cho có một con đường nối từ thị trấn ~x_i~ đến thị trấn ~x_{i+1}~ với mọi ~0 \le i < k~. Đảm bảo rằng không có chuyến đi nào có độ dài vô hạn ở ~X~, và không có hai con đường nào kết nối cùng một cặp thị trấn.

Đối với mỗi thị trấn, Aaron muốn biết chuyến đi dài nhất có thể bắt đầu từ đó. Với mỗi vị trí xuất phát, có nhiều chuyến đi dài nhất và trong số đó, Aaron thích chuyến đi có dãy các nhãn được đánh dấu trên đường đi có thứ tự từ điển nhỏ nhất. Một dãy được coi là nhỏ hơn từ điển so với một dãy khác cùng độ dài nếu, tại vị trí đầu tiên mà chúng khác nhau, phần tử đầu tiên của dãy này nhỏ hơn phần tử tương ứng của dãy kia.

Hãy in ra độ dài và tổng các nhãn đường đi của chuyến đi mà Aaron ưu tiên đi xuất phát từ mỗi thị trấn.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ (~1 \le N \le 2 \times 10^5, 1 \le M \le 4 \times 10^5~).
• ~M~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~a_i, b_i~ và ~l_i~ (~1 \le a_i, b_i \le N, 1 \le l_i \le 10^9~)

Output

• Gồm ~N~ dòng, mỗi dòng chứa hai số nguyên dương ~L_i~ và ~sum_i~ lần lượt là độ dài đường đi dài nhất và tổng các nhãn trên đường đi có thứ tự từ điển nhỏ nhất khi xuất phát từ thị trấn ~i~.

Subtasks

Example

Sample Input

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

Sample Output

0 0
1 10
1 5
2 12

Note

• Từ thị trấn ~1~ không đi được đến các thị trấn khác.
• Từ thị trấn ~2~ sẽ đi đến thị trấn ~1~, tổng nhãn là ~10~.
• Từ thị trấn ~3~ đi đến thị trấn ~1~, tổng nhãn là ~5~.
• Từ thị trấn ~4~ đi đến thị trấn ~2~ và thị trấn ~1~, tổng nhãn là ~12~. (Ta không chọn đường đi đến thị trấn ~3~ vì dãy (~2, 10~) có thứ tự từ điển nhỏ hơn (~4, 5~)).

Cho một đồ thị liên thông gồm ~N~ đỉnh và ~M~ cạnh (không tồn tại cạnh lặp và khuyên). Hãy đếm xem có bao nhiêu cạnh mà khi bỏ đi hai đầu kề của cạnh này khỏi đồ thị thì ~n-2~ đỉnh còn lại không còn liên thông?

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ (~1 \le N \le 10^5, 1 \le M \le 3 \cdot 10^5~).
• ~M~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u, v~ thể hiện có một cạnh hai chiều nối hai đỉnh u và đỉnh ~v~ (~1 \le u, v \le n~).

Output

• Gồm một dòng duy nhất in ra số cạnh thỏa mãn yêu cầu đề bài.

Subtask

Example

Sample Input

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

Sample Output

1

Note

Có duy nhất cạnh (~1, 3~) thỏa mãn.

Một đất nước có ~N~ thành phố được đánh số từ ~1~ đến ~N~ và có ~N-1~ đường cao tốc hai chiều. Mọi cặp thành phố đều có thể đi được đến nhau khi sử dụng các đường cao tốc này.

Khoảng cách giữa hai thành phố ~x~ và ~y~ là số đường cao tốc cần phải đi qua ít nhất để đi từ thành phố ~x~ đến thành phố ~y~.

Chính phủ quyết định sẽ phá một đường cao tốc và xây một cái cao tốc mới sao cho khoảng cách xa nhất giữa hai thành phố là lớn nhất.

Hãy tìm khoảng cách lớn nhất đó.

Input

• Dòng đầu gồm số nguyên dương ~N~ (~3 \le N \le 3 \times 10^5~).
• ~N - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u, v~ thể hiện có một đường đi hai chiều giữa hai thành phố ~u~ và thành phố ~v~ (~1 \le u, v \le N~).

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Subtask

Example

Sample Input

4
1 2 
1 3
3 4

Sample Output

3