Có hai hệ thống đường cao tốc được điều hành bởi hai Công ty A và B. Mỗi hệ thống đường bao gồm các nút và các đoạn đường nối các nút. Trên mặt phẳng toạ độ, các nút được biểu diễn bởi các điểm, và mỗi đoạn đường được biểu diễn bởi một đoạn thẳng nối 2 điểm tương ứng với hai nút.

Hai đoạn đường bất kỳ của hai hệ thống đường là không giao nhau ngoài ở nút đầu mút và mỗi hệ thống đường đều có tính liên thông, nghĩa là giữa hai nút bất kỳ luôn tìm được các đoạn đường liên tiếp nối chúng, và hơn nữa hai hệ thống đường là không giao nhau, tức là không tìm được nút nào thuộc cả hai hệ thống đường.

Sau một thời gian hoạt động, hai công ty A và B quyết định hợp nhất thành công ty AB nhằm nâng cao hiệu quả khai thác hệ thống đường cao tốc của họ. Vấn đề đặt ra đối với Ban Giám đốc công ty AB là hợp nhất hai hệ thống đường bằng cách xây dựng một đoạn đường thẳng nối hai nút thoả mãn các tính chất sau đây:

• Một nút thuộc hệ thống đường của Công ty A và một nút thuộc hệ thống đường của công ty B;
• Đoạn đường mới xây dựng không được có điểm chung với bất cứ đoạn đường nào của hai hệ thống đường của các công ty A và B ngoài ở hai đầu mút của đoạn đường mới này.

Yêu cầu: Giúp Ban Giám đốc công ty AB xác định đoạn đường cần xây dựng đáp ứng các yêu cầu đặt ra.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(T \le 5)~ là số lượng bộ dữ liệu.

• Tiếp đến là thông tin của ~T~ bộ dữ liệu. Mỗi bộ dữ liệu bao gồm hai nhóm dòng mô tả biểu diễn trên mặt phẳng của các hệ thống đường: nhóm thứ nhất mô tả hệ thống đường của công ty A, nhóm thứ hai mô tả hệ thống đường của công ty B. Mỗi nhóm dòng có khuôn dạng như sau:

  • Dòng đầu tiên chứa hai số nguyên dương ~N~ ~(2 \le N)~ và ~M~, trong đó ~N~ là số lượng nút còn ~M~ là số lượng đoạn đường trong hệ thống. Các nút được đánh số từ ~1~ đến ~N~.
  • Dòng thứ ~i~ trnog số ~N~ dòng tiếp theo chứa hai số nguyên ~x_i~ và ~y_i~ ~(-10^6 \le x_i, y_i \le 10^6)~ là toạ độ của nút thứ ~i~, ~i = 1, 2, \ldots, N~.
  • Mỗi dòng trong số ~M~ dòng tiếp theo chứa hai số nguyên ~p~ và ~q~ ~(1 \le p, q \le N, p \ne q)~ là các chỉ số của hai nút đầu mút của một đoạn đường.

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra ~T~ dòng tương ứng với kết quả của ~T~ bộ dữ liệu đầu vào, mỗi dòng ghi hai số nguyên ~a~ và ~b~ cách nhau bởi một dấu cách là hai đầu mút của đoạn đường tìm được, trong đó ~a~ là chỉ số của nút thuộc hệ thống đường của công ty A và ~b~ là chỉ số của nút thuộc hệ thống đường của công ty B (nếu không tìm được đoạn đường cần xây dựng đáp ứng các yêu cầu đặt ra thì ghi ra một số ~0~; trong trường hợp bài toán có nhiều lời giải, chỉ cần đưa ra một lời giải tuỳ ý).

Giới hạn

Ký hiệu ~N_A (N_B), M_A (M_B)~ theo thứ tự là số lượng nút và số lượng đoạn đường trong hệ thống đường của công ty A (công ty B).

• Có ~40\%~ số lượng test thoả mãn điều kiện: ~2 \le N_A, M_A, N_B, M_B \le 500~;
• Có thêm ~30\%~ số lượng test thoả mãn điều kiện: ~2 \le N_A, M_A, N_B, M_B \le 5\,000~; toạ độ của các nút trong cả hai hệ thống đường có trị tuyệt đối không vượt quá ~10^4~;
• ~30\%~ số lượng test còn lại thoả mãn điều kiện: ~2 \le N_A, N_B \le 200\,000; 1 \le M_A, M_B \le 700\,000~.

Sample Input

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

Sample Output

5 2

Note