Một liên danh nghiên cứu đang xây dựng một trung tâm dữ liệu mới. Trong trung tâm dữ liệu, một tập hợp các máy tính được thiết lập để cùng làm việc và liên lạc qua một mạng. Mạng chỉ có các liên kết trực tiếp hai chiều giữa các máy tính. Hai máy tính \(c_1\) và \(c_2\) không có liên kết trực tiếp vẫn có thể liên lạc nếu tồn tại ít nhất một đường đi gồm các liên kết \(l_1,l_2,\ldots,l_k\), sao cho \(l_i\) và \(l_{i+1}\) có chung một đầu mút, \(c_1\) là một đầu mút của \(l_1\), còn \(c_2\) là một đầu mút của \(l_k\). Giữa hai máy tính bất kỳ có nhiều nhất một liên kết trực tiếp.

Liên danh yêu cầu bạn nộp một thiết kế cho biết mạng có bao nhiêu máy tính và chúng được nối với nhau như thế nào. Mỗi thiết kế phải thỏa mãn tất cả các điều kiện sau:

1. Mạng có từ \(L\) đến \(U\) máy tính, kể cả hai đầu mút.
2. Mỗi máy tính là đầu mút của đúng 4 liên kết, nối nó với 4 máy tính phân biệt khác.
3. Mọi cặp máy tính đều có thể liên lạc với nhau theo định nghĩa ở trên.
4. Các máy tính phải có thể tự xác định duy nhất danh tính của mình ngay cả khi ID của chúng bị thay đổi ngẫu nhiên trong lúc hệ thống tắt.

Nói rõ hơn về điều kiện cuối: ban đầu, mỗi máy trong số \(N\) máy tính của một thiết kế được gán một số nguyên duy nhất từ 1 đến \(N\) làm ID. Tuy nhiên, sau một thời gian ngừng hoạt động, hệ thống có thể khởi động lại với các ID đã bị hoán vị: mỗi máy vẫn mang một số nguyên duy nhất từ 1 đến \(N\), nhưng không nhất thiết là ID ban đầu. Mạng phải khôi phục được các số định danh ban đầu mà không dùng bất kỳ thông tin nào ngoài các liên kết trực tiếp đang tồn tại.

Để đánh giá thiết kế, liên danh dùng một chương trình tự động. Chương trình nhận thiết kế của bạn, kiểm tra ba điều kiện đầu tiên, rồi gửi lại một bản sao của thiết kế với các thay đổi sau:

• Các ID duy nhất được hoán vị ngẫu nhiên; mỗi ID mới có xác suất như nhau được gán cho bất kỳ máy tính nào.
• Mỗi liên kết được viết với ID nhỏ hơn đứng trước, theo các ID mới.
• Toàn bộ tập liên kết được sắp tăng dần theo đầu mút thứ nhất, và nếu bằng nhau thì theo đầu mút thứ hai nhỏ hơn, tức theo thứ tự từ điển.

Bạn phải xác định chính xác các ID đã bị thay đổi như thế nào. Một cách hình thức, chương trình tự động tạo một hoán vị bí mật ngẫu nhiên \(f\) của các số nguyên từ 1 đến \(N\), rồi gán các số ấy cho các máy tính trong một “bản sao trắng” của mạng, nơi mọi liên kết cũ đã bị xóa. Với mỗi liên kết giữa máy \(i\) và máy \(j\) trong thiết kế của bạn, chương trình thêm vào bản sao một liên kết giữa \(f(i)\) và \(f(j)\). Sau đó, bạn phải tái tạo chính xác hoán vị \(f\) mà chương trình đã tạo. Nếu tồn tại một hoán vị khác \(f'\) cho cùng kết quả và bạn trả về \(f'\), liên danh sẽ không chấp nhận thiết kế: trong trường hợp đó, bạn không thể bảo đảm rằng các ID được khôi phục là ID ban đầu.

Với mọi \(N\) từ 10 đến 100, kể cả hai đầu mút, đề bảo đảm tồn tại ít nhất một mạng gồm \(N\) máy tính thỏa mãn mọi điều kiện trên và có tính chất rằng áp dụng hai hoán vị khác nhau \(f\) và \(f'\) sẽ tạo ra hai tập liên kết khác nhau.

Dữ liệu vào

Chương trình nhận dữ liệu từ bộ chấm theo giao thức tương tác bên dưới.

Dữ liệu ra

Chương trình gửi thiết kế mạng và câu trả lời tới bộ chấm theo giao thức tương tác bên dưới.

Giao thức tương tác

Ban đầu, đọc một dòng chứa số nguyên \(T\), là số lượng bộ test. Sau đó xử lý lần lượt \(T\) bộ test.

Với mỗi bộ test, trước tiên đọc một dòng chứa hai số nguyên \(L\) và \(U\), là khoảng giá trị cho phép, kể cả hai đầu mút, của số máy tính trong thiết kế mạng.

Tiếp theo, tạo một thiết kế có \(N\) máy tính và in \(2N+1\) dòng biểu diễn thiết kế đó. Dòng đầu chứa số nguyên \(N\). Mỗi dòng trong \(2N\) dòng còn lại chứa hai số nguyên \(A\) và \(B\), biểu diễn một liên kết khác nhau giữa hai máy \(A\) và \(B\), với \(A\ne B\). Nếu đã liệt kê liên kết A B, bạn không được liệt kê lại A B hoặc B A.

Sau khi đọc thiết kế, bộ chấm kiểm tra ba điều kiện đầu tiên trong đề. Nếu bất kỳ điều kiện nào không được thỏa mãn, bộ chấm gửi một dòng chỉ chứa -1, chấm dứt mọi liên lạc và chờ chương trình của bạn kết thúc. Nếu chương trình kết thúc bình thường và không vi phạm giới hạn khác, kết quả sẽ là Wrong Answer.

Nếu cả ba điều kiện đều được thỏa mãn, bộ chấm gửi \(2N+1\) dòng. Dòng đầu chứa số nguyên \(N\), đúng bằng \(N\) bạn đã gửi. Mỗi dòng trong \(2N\) dòng tiếp theo chứa hai số nguyên mô tả các liên kết của bản sao thiết kế, cùng định dạng với thiết kế bạn gửi. Bản sao được tạo theo cách đã mô tả ở trên; hoán vị \(f\) được chọn đều ngẫu nhiên trong tất cả các hoán vị có thể và độc lập với thiết kế mạng của bạn.

Để kết thúc bộ test, gửi cho bộ chấm một dòng gồm \(N\) số nguyên \(X_1,X_2,\ldots,X_N\). Với mọi \(i\), \(X_i\) có nghĩa là máy tính mà bạn đã gán số \(i\) được gán số \(X_i\) trong bản sao của bộ chấm; nói cách khác, \(X_i=f(i)\).

Nếu danh sách này không đúng với danh sách bộ chấm đã tạo, bạn sẽ nhận Wrong Answer. Nếu đây là bộ test cuối cùng, bộ chấm không gửi thêm gì. Nếu chưa phải bộ test cuối, bộ chấm gửi một dòng chỉ chứa -1 rồi ngừng liên lạc. Trong cả hai trường hợp, bộ chấm chờ chương trình kết thúc và chỉ gán Wrong Answer nếu chương trình kết thúc bình thường mà không vi phạm giới hạn tài nguyên nào khác. Khi nhận -1, chương trình nên kết thúc ngay.

Không gửi thêm thông tin cho bộ chấm sau khi giải xong tất cả các bộ test. Cụ thể, nếu chương trình tiếp tục in ra đầu ra chuẩn sau danh sách các \(X_i\) của bộ test cuối, bạn sẽ nhận Wrong Answer.

Bạn được phép dùng cùng một thiết kế mạng cho nhiều bộ test, miễn là thiết kế đó thỏa mãn mọi điều kiện của từng bộ test. Ngoài ra, seed sinh ngẫu nhiên của bộ chấm là cố định, nên nếu gửi cùng một dãy thiết kế gốc theo cùng thứ tự, bạn sẽ nhận lại cùng một dãy bản sao.

Ràng buộc

• \(1\le T\le 30\).

Phân nhóm

• Test Set 1 (hiển thị): \(L=10\) và \(U=50\).
• Test Set 2 (ẩn): \(10\le L\le 50\) và \(L=U\).

Ví dụ

  t = readline_int()           // reads 2 into t
  limits = readline_int_list() // reads 6 50 into limits
  printline 6 to stdout        // using 6 computers. Contestant designs an
                               //   octahedral network
  printline 2 4 to stdout
  printline 1 2 to stdout      // you do not need to list edges in any
                               //   particular order
  printline 3 1 to stdout      // you do not need to give the endpoints of a
                               //   link in order
  printline 1 4 to stdout
  printline 1 5 to stdout
  printline 2 3 to stdout
  printline 2 6 to stdout
  printline 3 5 to stdout
  printline 3 6 to stdout
  printline 4 5 to stdout
  printline 4 6 to stdout
  printline 5 6 to stdout
  flush stdout                 // judge verifies that the network meets
                               //   conditions 1-3 above, and secretly picks
                               //   2 6 3 1 5 4 as the new permutation
  n = readline_int()           // reads 6 into n
  repeat 12 times:
    add readline_int_list() to edges  // reads 1 2, 1 4, 1 5, 1 6, 2 3, 2 5,
                                      //   2 6, 3 4, 3 5, 3 6, 4 5, 4 6, in
                                      //   that order
  printline 2 5 6 1 3 4        // note that this is consistent with what the
                               //   judge sent, but is not the permutation the
                               //   judge used
  flush stdout                 // judge decides that this is wrong
  limits = readline_int_list() // expects to read the next case but gets -1,
                               //   indicating a wrong answer
  exit                         // exits to avoid an ambiguous TLE error

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử đi kèm để chạy cục bộ hoặc trên nền tảng chính thức. Khi chạy cục bộ, cần chạy công cụ song song với chương trình của bạn; có thể dùng interactive runner. Hãy đọc hướng dẫn trong phần bình luận của tệp đó và phần Bài tương tác trong FAQ.

Hướng dẫn riêng của công cụ cũng nằm trong các bình luận bên trong công cụ. Bạn nên bổ sung các bộ test của mình. Dù công cụ được thiết kế để mô phỏng hệ thống chấm, nó không phải hệ thống chấm thật và có thể hoạt động khác. Nếu chương trình vượt qua công cụ nhưng không vượt qua bộ chấm thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm bạn dùng cùng trình biên dịch với hệ thống chính thức.

Tải công cụ kiểm thử

Nguồn

Google Code Jam 2018, Vòng 3, bài Name-Preserving Network.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.