Vào năm 21XX, Vương quốc JOI quyết định di dân đến hành tinh IOI mới được phát hiện.

Vương quốc có \(N\) dân tộc, đánh số từ \(1\) đến \(N\), và có \(M\) cặp dân tộc có quan hệ hữu nghị. Trên hành tinh IOI có \(L\) khu dân cư, đánh số từ \(1\) đến \(L\), với \(L\ge N\). Khu dân cư \(i\) là điểm \(P_i=(X_i,Y_i)\) trên mặt phẳng tọa độ.

Bạn phải gán cho mỗi dân tộc đúng một khu dân cư, và không khu dân cư nào được gán cho nhiều hơn một dân tộc. Với mỗi cặp dân tộc có quan hệ hữu nghị, một đường ray thẳng sẽ nối hai khu dân cư của họ. Hai đường ray có thể cắt nhau tùy theo cách gán.

Mục tiêu là đưa ra một phương án làm nhỏ nhất số cặp đường ray cắt nhau.

Dữ liệu vào

Bài có năm bộ dữ liệu công khai, mỗi bộ tương ứng với một nhóm. Mỗi tệp có định dạng:

• Dòng đầu gồm \(N,M\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) gồm \(A_j,B_j\), biểu thị hai dân tộc có quan hệ hữu nghị.
• Dòng tiếp theo chứa \(L\).
• \(L\) dòng tiếp theo, dòng thứ \(i\) gồm \(X_i,Y_i\), là tọa độ khu dân cư \(P_i\).

Dữ liệu ra

Với mỗi tệp đầu vào, nộp một tệp đầu ra gồm \(N\) dòng. Dòng thứ \(k\) chứa chỉ số khu dân cư được gán cho dân tộc \(k\).

Các chỉ số được in phải đôi một khác nhau và nằm trong đoạn \([1,L]\).

Ràng buộc

• \(1 \le A_j,B_j \le N\).
• \(1 \le X_i,Y_i \le 100\,000\).
• Không có ba điểm \(P_i,P_j,P_k\) nào thẳng hàng.
• Đồ thị hữu nghị liên thông.
• Có thể có nhiều hơn hai đường ray cùng giao nhau tại một điểm.

Phân nhóm

Mỗi nhóm gồm đúng một tệp đầu vào công khai và có tối đa 20 điểm.

Chấm điểm

Nếu phương án không thỏa mãn các điều kiện của đề, nhóm đó nhận \(0\) điểm.

Nếu phương án hợp lệ, gọi \(C\) là số cặp đường ray cắt nhau. Điểm của nhóm có các tham số \(S,T\) được tính như sau:

Trong đó \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Tổng điểm của bài là tổng điểm của năm nhóm, tối đa 100 điểm.

Ví dụ

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

1
5
4
2
7
3