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

Một nhóm cướp biển có một bản đồ về một vùng biển rộng lớn để chiếm đoạt được kho báu. Đảo mà chúng sống được đánh dấu bằng chữ o. Các tên cướp có thể bắt đầu hành trình của họ ở bất kỳ một trong bốn hướng. Các dòng chảy biển ở vùng biển này di chuyển theo một trong bốn hướng và được đánh dấu như sau: từ phía tây sang phía đông >, từ phía đông sang phía tây <, từ phía bắc sang phía nam v và từ phía nam sang phía bắc ^. Khi các tên cướp đang ở trên một ô có dòng chảy, chúng sẽ di chuyển sang ô khác theo hướng của dòng chảy.

Ô biển lặng được đánh dấu bằng dấu chấm .. Nếu dòng chảy đưa các tên cướp đến một ô biển lặng, hoặc đưa họ ra khỏi bản đồ, hoặc quay trở lại đảo xuất phát, họ sẽ dừng hành trình của mình. Đảo mà các tên cướp muốn đến được đang có kho báu đánh dấu bằng x.

Với việc phải di chuyển theo các dòng chảy, con thuyền của những tên cướp biển này có thể đi vào một vòng xoáy không lối thoát và có thể không đến được hòn đảo đang nắm giữ kho báu. Tuy nhiên, con thuyền của chúng cũng có sức mạnh thần kì: nó có thể đi khác hướng với dòng chảy, có thể tùy ý đi sang một hướng bất kì mà không phải hướng của dòng chảy. Tuy nhiên, nếu sử dụng quá nhiều lần sức mạnh có thể khiến thuyền bị hư hỏng. Nhiệm vụ của bạn là hãy sử dụng ít điểm sức mạnh nhất có thể để đi đến đích.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 2000)~ là kích thước vùng biển.
• ~n~ dòng tiếp theo, mỗi dòng gồm một dãy kí tự o<>v^.x thể hiện dòng chảy hoặc vị trí bắt đầu / kết thúc. Lưu ý có duy nhất một kí tự o và một kí tự x.

Output

Dòng đầu tiên gồm số nguyên dương ~k~ - số lần con thuyền cần sử dụng sức mạnh ít nhất. ~n~ dòng tiếp theo, mỗi dòng gồm dãy ~m~ kí tự, miêu tả một bản đồ mới khác bản đồ ban đầu đúng ~k~ ô mà tại ~k~ ô này, con thuyền sử dụng sức mạnh để có thể đi đến nơi đảo chứa kho báu.

Subtask

• Subtask ~1~ ~(30\%)~: ~3 \le n, m \le 20~.
• Subtask ~2~ ~(70\%)~: Không có điều kiện gì thêm.

Sample Input 1

3 3
>vo
vv>
x>>

Sample Ouput 1

1

Explanation 1

Có thể dùng sức mạnh ở ô ~(3, 2)~

>vo
vv>
x<>

Sample Input 2

4 4
x.v.
.>.<
>.<.
.^.o

Sample Output 2

4

Explanation 2

Một cách sử dụng sức mạnh như sau:

x<<.
.>^<
>.<^
.^.o

Một công ty có ~n~ nhân viên đang trong quá trình tái cơ cấu tổ chức. Sau quá trình này, sơ đồ cấp bậc trong công ty tạo thành một đồ thị dạng cây gồm ~n~ đỉnh, mỗi đỉnh là sếp của tất cả các con của chúng.

Mỗi nhân viên có một danh sách gồm ~k_i~ người họ đồng ý làm sếp trực tiếp của mình. Ngoài ra, mỗi nhân viên cần được tính toán lại lương sao cho lương của mỗi người sếp phải lớn hơn tổng lương của những nhân viên người đó quản lí.

Hãy tìm cách tái cơ cấu lại công ty sao cho tổng lương phải trả cho ~n~ nhân viên là nhỏ nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - số nhân viên trong công ty.
• ~n~ dòng tiếp theo, mỗi dòng bắt đầu bởi số nguyên ~k_i~. Sau đó là ~k_i~ số nguyên dương là danh sách những người được nhân viên thứ ~i~ đồng ý làm sếp của mình.

Output

• Gồm một số nguyên dương là tổng lương phải trả nhỏ nhất.

Subtask

• Subtask 1 ~(20\%)~: ~2 \le n \le 10, \sum{k_i} \le 20~
• Subtask 2 ~(45\%)~: ~2 \le n \le 200, \sum{k_i} \le 200~.
• Subtask 3 ~(35\%)~: ~2 \le n \le 5000, \sum{k_i} \le 10000~.

Sample Input 1

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

Sample Output 1

8

Explanation 1

    3
   / \ 
  4   2
 /
1

Lương của từng người là ~[1, 1, 2, 4]~.

Cho một cây có ~n~ đỉnh đánh số từ ~1~ đến ~n~ và đỉnh ~1~ là gốc. Mỗi đỉnh trên đều được tô màu, đỉnh thứ ~i~ được tô bởi màu ~a_i~.

Một tập hợp các đỉnh trên được gọi là đẹp nếu có hơn một nửa số đỉnh trong tập được tô bởi cùng một màu.

Có ~q~ truy vấn, mỗi truy vấn thuộc một trong các dạng sau:

• Truy vấn dạng: ~1~ ~u~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trong cây con gốc ~u~ có phải là một tập đẹp hay không;
• Truy vấn dạng: ~2~ ~u~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm ngoài cây con gốc ~u~ có phải là một tập đẹp hay không;
• Truy vấn dạng: ~3~ ~u~ ~v~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trên đường đi đơn từ ~u~ tới ~v~ (tính cả ~u~ và ~v~) có phải là một tập đẹp hay không.
  
  

Input

• Dòng đầu tiên chứa số nguyên dương ~n, q~ là số đỉnh của cây và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số, số thứ ~i~ là ~a_i~ mô tả màu sắc của đỉnh ~i~. ~(1 \le a_i \le n)~
• ~n - 1~ dòng tiếp theo, mối dòng chứa hai số nguyên dương ~u, v~ ~(1 \le u, v \le n)~ mô tả cạnh nối hai đỉnh ~u~ và ~v~.
• Tiếp theo gồm có ~q~ dòng mô tả các truy vấn. Các truy vấn thuộc ~1~ trong ~3~ dạng ~1~ ~u~, ~2~ ~u~ hoặc ~3~ ~u~ ~v~.
  
  

Output

• Với mỗi truy vấn, in ra kết quả lần lượt trên các dòng khác nhau.
  
  

Constraints

• ~1 \le n,q \le 50000~
  
  

Subtasks

• Subtask ~1~ ~(20\%)~: ~1 ≤ n, q ≤ 2 000~.
• Subtask ~2~ ~(20\%)~: ~1 ≤ n, q ≤ 50 000~ và mỗi đỉnh có tối đa ~2~ cạnh nối trực tiếp.
• Subtask ~3~ ~(20\%)~: ~1 ≤ n, q ≤ 50 000~ và ~1 ≤ ai ≤ 2~
• Subtask ~4~ ~(20\%)~: ~1 ≤ n, q ≤ 50 000~ và không có truy vấn loại ~3~.
• Subtask ~5~ ~(20\%)~: không có ràng buộc nào thêm.
  
  

Sample Test

Input:

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

Output:

1
-1
-1
3
2

Giải thích:

Dưới đây là hình vẽ của ví dụ thứ nhất với màu ~1~ được tô màu xám, màu ~2~ được tô màu đỏ và màu ~3~ được tô màu xanh.

• Truy vấn ~1~: xét các đỉnh trong cây con gốc ~2~ là ~{2, 4, 5, 6, 8}~, màu ~1~ xuất hiện ~3~ lần.
• Truy vấn ~2~: xét các đỉnh trên đường đi từ ~4~ đến ~6~ là ~{2, 4, 5, 6}~, không có màu nào xuất hiện quá ~2~ lần.
• Truy vấn ~3~: xét các đỉnh nằm ngoài cây con gốc ~6~ là ~{11, 2, 3, 4, 5, 7}~, không có màu nào xuất hiện quá ~13~ lần.
• Truy vấn ~4~: xét các đỉnh nằm ngoài cây con gốc ~5~ là ~{1, 2, 3, 4, 7}~, màu ~3~ xuất hiện ~3~ lần.
• Truy vấn ~5~: xét các đỉnh nằm trên đường đi từ ~1~ đến ~5~ là ~{1, 2, 5}~, màu ~2~ xuất hiện ~2~ lần.