Để trang trí cho buổi lễ bế mạc của kỳ thi Olympic truyền thống 30 tháng 4, Phong dự định thiết kế một mạng lưới gồm các bóng đèn và dây đèn treo trên trần nhà. Mỗi dây đèn kết nối chính xác hai bóng đèn, và giữa mỗi cặp bóng đèn bất kỳ có không quá một dây đèn. Phong định nghĩa khoảng cách giữa hai bóng đèn là số lượng dây đèn ít nhất kết nối thông qua các bóng đèn trung gian. Trong ngôn ngữ đồ thị, mạng lưới Phong muốn xây dựng là một đồ thị vô hướng không trọng số, với mỗi đỉnh tương ứng với một bóng đèn, mỗi cạnh tương ứng với một dây đèn nối hai bóng đèn và khoảng cách giữa hai bóng đèn là đường đi qua ít cạnh nhất giữa hai đỉnh tương ứng.

Hiện tại, Phong đã có sẵn ~N~ bóng đèn màu với các màu sắc khác nhau, các bóng đèn này được đánh số từ ~1~ đến ~N~, và chưa có dây đèn nào. Phong muốn có một buổi lễ đáng nhớ với sự phân bố hợp lý giữa ~N~ bóng đèn màu. Phong chuẩn bị một ma trận ~A~ kích thước ~N \times N~, trong đó ~A_{ij}~ là độ hợp lý giữa bóng đèn màu thứ ~i~ và bóng đèn màu thứ ~j~ với mong muốn xây dựng mạng lưới sao cho ~A_{ij}~ bằng khoảng cách giữa chúng. Do đó, Phong có thể phải mua thêm một số bóng đèn trắng và dây đèn để hoàn thiện mạng lưới theo ý của mình. Do ngân sách cho buổi lễ hạn chế nên Phong muốn tìm cách mua thêm ít bóng đèn trắng nhất có thể (không có giới hạn về số lượng dây đèn phải mua thêm). Số lượng dây đèn Phong phải mua thêm là số lượng dây đèn trong phương án dựng mạng lưới sử dụng ít bóng đèn trắng nhất mà Phong tìm được.

Yêu cầu: Hãy giúp Phong tìm ra một phương án hợp lệ xây dựng mạng lưới sử dụng ít bóng đèn trắng nhất.

Input

• Dòng đầu chứa một số nguyên dương ~N~ là số bóng đèn màu ~(2 \le N \le 10)~.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa ~N~ số nguyên không âm ~A_{i1}, A_{i2}, \dots, A_{iN}~ là độ hợp lý giữa các cặp bóng đèn màu ~(A_{ii}=0; 1 \le A_{ij}=A_{ji} \le 10, \forall i \ne j)~.

Output

• Nếu không tồn tại phương án thỏa mãn, in ra -1 -1 (hai số -1) trên một dòng.

• Ngược lại, in ra kết quả theo định dạng sau:

  • Dòng đầu gồm hai số nguyên ~K~ và ~M~ lần lượt là số lượng bóng đèn trắng và số lượng dây đèn mà Phong phải mua thêm.

  • Mỗi dòng trong số ~M~ dòng tiếp theo gồm hai số nguyên dương ~i~ và ~j~ mô tả một dây đèn kết nối bóng đèn thứ ~i~ và bóng đèn thứ ~j~ ~(1 \le i < j \le N+K)~. Các bóng đèn trắng mà Phong mua thêm được đánh số từ ~N+1~ đến ~N+K~.

Lưu ý: có thể chứng minh được rằng nếu tồn tại phương án thỏa mãn thì cũng tồn tại một phương án thỏa mãn mà không phải mua thêm quá ~500~ bóng đèn trắng.

Scoring

Đối với mỗi test, gọi ~K_P~ là số lượng bóng đèn trắng phải mua thêm trong phương án của bạn và ~K_J~ là số lượng bóng đèn trắng phải mua thêm trong phương án của Ban giám khảo:

• Nếu ~K_P \le K_J~, bạn được ~100\%~ số điểm của test đó.

• Nếu ~K_P > K_J+400~, bạn được ~0~ điểm cho test đó.

• Nếu ~K_J < K_P \le K_J+400~, phần trăm số điểm của bạn cho test đó được tính theo công thức:

  ~S=\left(1-\sqrt[4]{\dfrac{K_P-K_J-0.75}{400}}\right)\times 100\%~.

Subtask 1 gồm chín test cố định sau:

• Test 1 — ~0,36~ điểm, ~K_J=0~:

  4
  0 1 2 1
  1 0 1 2
  2 1 0 1
  1 2 1 0
  

• Test 2 — ~0,36~ điểm, ~K_J=0~:

  5
  0 1 1 1 1
  1 0 1 1 1
  1 1 0 1 1
  1 1 1 0 1
  1 1 1 1 0
  

• Test 3 — ~0,36~ điểm, ~K_J=29~:

  7
  0 10 10 10 10 10 10
  10 0 10 10 10 10 10
  10 10 0 10 10 10 10
  10 10 10 0 10 10 10
  10 10 10 10 0 10 10
  10 10 10 10 10 0 10
  10 10 10 10 10 10 0
  

• Test 4 — ~0,36~ điểm, ~K_J=40~:

  10
  0 9 9 9 9 9 9 9 9 9
  9 0 9 9 9 9 9 9 9 9
  9 9 0 9 9 9 9 9 9 9
  9 9 9 0 9 9 9 9 9 9
  9 9 9 9 0 9 9 9 9 9
  9 9 9 9 9 0 9 9 9 9
  9 9 9 9 9 9 0 9 9 9
  9 9 9 9 9 9 9 0 9 9
  9 9 9 9 9 9 9 9 0 9
  9 9 9 9 9 9 9 9 9 0
  

• Test 5 — ~0,36~ điểm, ~K_J=1~:

  8
  0 2 2 2 1 2 2 1
  2 0 2 4 3 1 2 3
  2 2 0 2 3 2 2 1
  2 4 2 0 3 4 4 1
  1 3 3 3 0 3 3 2
  2 1 2 4 3 0 2 3
  2 2 2 4 3 2 0 3
  1 3 1 1 2 3 3 0
  

• Test 6 — ~0,60~ điểm, ~K_J=13~:

  4
  0 9 7 8
  9 0 10 7
  7 10 0 9
  8 7 9 0
  

• Test 7 — ~0,60~ điểm, ~K_J=3~:

  5
  0 1 2 3 4
  1 0 1 3 4
  2 1 0 2 3
  3 3 2 0 2
  4 4 3 2 0
  

• Test 8 — ~0,60~ điểm, ~K_J=1~:

  10
  0 2 2 3 2 3 3 3 1 2
  2 0 1 2 1 1 2 1 2 2
  2 1 0 3 2 1 1 2 3 2
  3 2 3 0 1 3 2 3 2 3
  2 1 2 1 0 2 1 2 1 2
  3 1 1 3 2 0 2 2 3 3
  3 2 1 2 1 2 0 1 2 3
  3 1 2 3 2 2 1 0 3 3
  1 2 3 2 1 3 2 3 0 1
  2 2 2 3 2 3 3 3 1 0
  

• Test 9 — ~0,60~ điểm, ~K_J=38~:

  10
  0 7 9 6 6 6 8 5 5 6
  7 0 8 7 8 7 9 6 4 6
  9 8 0 8 9 9 7 10 9 8
  6 7 8 0 8 4 7 7 6 4
  6 8 9 8 0 7 8 4 6 7
  6 7 9 4 7 0 5 7 5 2
  8 9 7 7 8 5 0 6 5 6
  5 6 10 7 4 7 6 0 5 5
  5 4 9 6 6 5 5 5 0 6
  6 6 8 4 7 2 6 5 6 0
  

Sample Input 1

4
0 1 1 1
1 0 2 2
1 2 0 2
1 2 2 0

Sample Output 1

0 3
1 2
1 3
1 4

Sample Input 2

4
0 1 1 2
1 0 2 1
1 2 0 2
2 1 2 0

Sample Output 2

1 5
1 2
1 3
2 4
3 5
4 5

Notes

Phong không cần phải mua thêm bóng đèn trắng nào trong ví dụ thứ nhất mà chỉ cần nối các bóng đèn màu như kết quả đã cho.

Trong ví dụ thứ hai, một phương án tối ưu là Phong mua thêm một bóng đèn trắng và nối các bóng đèn như kết quả đã cho.