Bạn được cung cấp hai ma trận, \(A\) và \(B\), mỗi ma trận có \(H\) hàng và \(W\) cột.

Với mỗi cặp số nguyên \((i,j)\) thỏa mãn \(1≤i≤H\) và \(1≤j≤W\), Chúng ta coi \((i,j)\) đại diện cho ô ở hàng thứ \(i\) và cột thứ \(j\). Trong ma trận \(A\), ô \((i,j)\) chứa số nguyên \(A_{(i,j)}\). Trong ma trận \(B\), ô \((i,j)\) chứa số nguyên \(B_{(i,j)}\).

Bạn sẽ lặp lại thao tác sau bất kỳ số lần nào, có thể là không lần nào. Trong mỗi thao tác, bạn thực hiện một trong các hành động sau:

• Chọn một số nguyên \(i\) thỏa mãn \(1≤i≤H-1\) và hoán đổi hàng thứ \(i\) và hàng \((i+1)\) trong ma trận \(A\).
• Chọn một số nguyên \(i\) thỏa mãn \(1≤i≤W-1\) và hoán đổi cột thứ \(i\) và cột \((i+1)\) trong ma trận \(A\).

Hãy xác định liệu có thể làm cho ma trận \(A\) giống hệt ma trận \(B\) bằng cách lặp lại thao tác trên hay không. Nếu có thể, in ra số lượng thao tác tối thiểu cần thiết để làm điều đó.

Ở đây, ma trận \(A\) giống hệt lưới \(B\) nếu và chỉ nếu, với tất cả các cặp số nguyên \((i,j)\) thỏa mãn \(1≤i≤H\) và \(1≤j≤W\), số nguyên được viết trong ô \((i,j)\) của ma trận \(A\) bằng với số nguyên được viết trong ô \((i,j)\) của ma trận \(B\).

INPUT FORMAT

Dòng đầu tiên nhập vào hai số nguyên \(H\) và \(W\) \((2 \leq H, W \leq 5)\).

Các dòng tiếp theo sẽ chứa ma trận \(A\) và ma trận \(B\) \((1 \leq A_{i,j}, B_{i,j} \leq 10^9)\).

OUTPUT FORMAT

In ra một số nguyên là số thao tác biến đổi ma trận \(A\) thành ma trận \(B\), Nếu ko thể làm điều đó hãy in ra \(-1\).

Ví dụ:

Input

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
1 3 2 5 4
11 13 12 15 14
6 8 7 10 9
16 18 17 20 19

Output

3

Ví dụ:

Input

2 2
1 1
1 1
1 1
1 1000000000

Output

-1

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House