CosmicBrew

Cuội quyết định mở dịch vụ Giao Trà Sữa Xuyên Ngân Hà.

Ngân Hà được mô phỏng bằng một lưới gồm \(R\) hàng và \(C\) cột. Có \(N\) Hòn Đảo Bay, được đánh số từ \(1\) đến \(N\). Đảo thứ \(i\) nằm tại ô có tọa độ \((X_i,Y_i)\). Các đảo nằm tại những ô đôi một khác nhau.

Ban đầu, Cuội đang ở đảo \(1\). Cuội cần giao trà sữa đến tất cả các đảo từ \(2\) đến \(N\), mỗi đảo đúng một lần, sau đó quay trở lại đảo \(1\).

Tại một ô \((x,y)\), gọi \(d(x \times y)\) là số lượng ước nguyên dương của \(x \times y\). Nếu \(d(x \times y)\) là một số lẻ thì ô đó chứa Bẫy Sấm Sét.

Tương đương, ô \((x,y)\) chứa bẫy khi và chỉ khi: \(x \times y\) là một số chính phương.

Cuội không được đi vào hoặc bay qua một ô chứa bẫy. Nếu một Hòn Đảo Bay nằm trên ô chứa bẫy thì Cuội không thể hoàn thành việc giao hàng.

Từ một ô không chứa bẫy, Cuội có thể di chuyển sang một trong bốn ô chung cạnh:

Ô được di chuyển tới phải nằm trong lưới và không chứa bẫy. Mỗi lần di chuyển tốn \(1\) đơn vị năng lượng.

Năng lượng cần thiết để đi từ đảo \(u\) đến đảo \(v\) là số bước ít nhất cần thực hiện để đi từ ô chứa đảo \(u\) đến ô chứa đảo \(v\).

Trong khi di chuyển giữa hai đảo, Cuội có thể đi qua ô chứa một đảo khác. Việc đi qua như vậy không được tính là giao hàng tại đảo đó. Một đảo chỉ được xem là đã được giao hàng khi Cuội chọn đảo đó làm điểm đến tiếp theo trong hành trình.

Ngoài ra, giữa các đảo có \(M\) Cổng Không Gian một chiều. Cổng \((u,v)\) có hướng từ đảo \(u\) đến đảo \(v\).

Các Cổng Không Gian không được sử dụng để di chuyển và không ảnh hưởng đến năng lượng của hành trình. Chúng chỉ được dùng để kiểm tra điều kiện kích hoạt hệ thống giao hàng.

Hệ thống được kích hoạt nếu đồ thị gồm \(N\) đảo và \(M\) cổng là liên thông yếu. Nói cách khác, sau khi bỏ qua hướng của tất cả các cổng, từ một đảo bất kỳ phải có thể đi đến tất cả các đảo còn lại thông qua các cổng.

Hãy tìm tổng năng lượng nhỏ nhất của một hành trình thỏa mãn:

• Bắt đầu tại đảo \(1\);
• Giao hàng tại mỗi đảo từ \(2\) đến \(N\) đúng một lần;
• Quay trở lại đảo \(1\) sau khi đã giao hàng tại tất cả các đảo.

Nếu hệ thống cổng không liên thông yếu, có đảo nằm trên ô chứa bẫy hoặc tồn tại hai đảo không thể di chuyển qua lại bằng các ô không chứa bẫy, hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(R\), \(C\), lần lượt là số đảo, số cổng, số hàng và số cột của lưới (\(1 \le N \le 15\);\(0 \le M \le 50\); \(1 \le R,C \le 100\)).

• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), mô tả tọa độ của đảo thứ \(i\) (\(1 \le X_i \le R\), \(1 \le Y_i \le C\)).

Các tọa độ \((X_i,Y_i)\) đôi một khác nhau. Đảo \(1\) là vị trí xuất phát của Cuội.

• Trong \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\), mô tả một cổng một chiều từ đảo \(u\) đến đảo \(v\) (\(1 \le u,v \le N\), \(u \ne v\)).

Output

• In ra một số nguyên duy nhất là tổng năng lượng nhỏ nhất để Cuội hoàn thành việc giao hàng.
• Nếu không thể hoàn thành, in ra \(-1\).

Example

2 1 2 3
1 2
1 3
1 2

2

6 5 8 9
1 2
2 9
8 9
5 6
1 8
4 5
1 3
4 2
3 5
6 4
5 6

36

Scoring

• Subtask 1 (60% điểm): \(N \le 5\) và \(R,C \le 10\)

• Subtask 2 (40% điểm): Không có ràng buộc bổ sung.