Tính ngẫu nhiên hiện hữu ở khắp mọi nơi, xuyên suốt cuộc đời mỗi con người. Ngay cả trong những cuộc thi quan trọng nhất, yếu tố quyết định thắng bại đôi khi chỉ là vận may.

Vào năm 2035, có $n$ người hâm mộ cuồng nhiệt của trò chơi "Clash Royale" muốn so tài cao thấp. Để đảm bảo công bằng, họ quyết định đấu với nhau theo thể thức vòng tròn, tổng cộng diễn ra $\frac{n(n-1)}{2}$ trận đấu.

Tuy nhiên, vào thời điểm đó, "Clash Royale" đã hoàn toàn biến thành trò chơi "Oẳn tù tì"! Do đó, trong mỗi trận đấu, xác suất thắng của cả hai bên đều là 50% và độc lập với nhau.

Người chơi thua cuộc tất nhiên sẽ cảm thấy không cam tâm. Để đạt được "chiến thắng tinh thần", họ đưa ra khái niệm "chiến thắng gián tiếp": Định nghĩa $u$ là $k$-chiến thắng gián tiếp $v$ khi và chỉ khi tồn tại $k$ người $a_1, \dots, a_k$ sao cho $u$ thắng $a_1$, $a_1$ thắng $a_2$, $a_i$ thắng $a_{i+1}$ ($\forall i \in [1, k)$), và $a_k$ thắng $v$.

Đặc biệt, nếu $u$ trực tiếp thắng $v$, thì được gọi là 0-chiến thắng gián tiếp.

Các người chơi nảy sinh một thắc mắc mới: Với hai người chơi $u$ và $v$ cho trước, cần tối thiểu bao nhiêu tầng quan hệ gián tiếp để có thể nói $u$ thắng $v$?

Nói cách khác, bạn cần tìm số nguyên $k$ nhỏ nhất sao cho $u$ có thể $k$-chiến thắng gián tiếp $v$. Vì có rất nhiều người chơi không cam tâm, bạn cần trả lời $q$ truy vấn.

Dữ liệu vào

Lưu ý: Lượng dữ liệu vào của bài toán này khá lớn, khuyến khích sử dụng các phương thức đọc và ghi dữ liệu nhanh, ví dụ: trong C++ sử dụng scanf/printf hoặc cin/cout đã tắt đồng bộ hóa luồng. Khuyến khích tránh sử dụng các ngôn ngữ có tốc độ đọc ghi chậm.

Dòng đầu tiên chứa hai số nguyên $n, q$ ($2 \le n \le 5000, 1 \le q \le 10^5$).

$n-1$ dòng tiếp theo, dòng thứ $i$ là một chuỗi nhị phân độ dài $n-i$, trong đó chữ số thứ $j$ ($1 \le j \le n-i$) là 1 biểu thị người thứ $i$ thắng người thứ $i+j$, ngược lại nếu là 0 thì người thứ $i+j$ thắng người thứ $i$. Đảm bảo quan hệ thắng thua được tạo ra ngẫu nhiên độc lập với xác suất mỗi bên là 50%.

$q$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) biểu thị truy vấn thứ $i$.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ chứa một số nguyên $k$ biểu thị giá trị $k$ nhỏ nhất sao cho $u_i$ là $k$-chiến thắng gián tiếp $v_i$. Đặc biệt, nếu với mọi $k$, $u_i$ không thể $k$-chiến thắng gián tiếp $v_i$, thì in ra -1.

Ví dụ

Ví dụ 1

4 12
110
11
1
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

Ví dụ 1

0
0
1
1
0
0
1
2
0
0
1
1

Ví dụ 2

5 20
0011
001
01
1
1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5
4 1
4 2
4 3
4 5
5 1
5 2
5 3
5 4

Ví dụ 2

1
1
0
0
0
2
1
0
0
0
1
0
1
0
0
0
-1
-1
-1
-1