Đã đến lúc đón Giáng sinh! Trong khi hầu hết các nơi làm việc đều tham gia trao đổi quà Secret Santa, nơi làm việc của bạn lại đang ấp ủ một âm mưu nham hiểm hơn: khám phá những bí mật của ông già Noel.

Ông già Noel có một danh sách "ngoan hay hư" cho mọi người trên Trái Đất. Vì nội dung danh sách rất nhạy cảm, nó được viết bằng tiếng North-Polish, một ngôn ngữ cổ với $N$ chữ cái. Để bảo mật hơn, ông già Noel đã mã hóa danh sách này bằng một mật mã thay thế: một hoán vị $H$ của các số $1, 2, \dots, N$, ánh xạ mỗi chữ cái $i$ trong tiếng North-Polish sang một chữ cái khác biệt $H(i)$. Trong mật mã như vậy, không có hai chữ cái nào ánh xạ tới cùng một chữ cái đích—nói một cách hình thức, nếu $i \neq j$ thì $H(i) \neq H(j)$—vì nếu không, ông già Noel sẽ không thể giải mã danh sách của mình! (Ông già Noel có thể chọn ánh xạ một số chữ cái sang chính nó, $H(i) = i$, chỉ để tăng thêm phần lắt léo.)

May mắn thay cho bạn, máy chủ của ông già Noel được lập trình khá sơ sài và bị lộ trên Internet công cộng. Bạn và các đồng nghiệp hy vọng sẽ hack vào máy chủ của ông già Noel, giải mã danh sách của ông ấy và xác nhận rằng tất cả các bạn đều là những đứa trẻ hư! (Hacker thì luôn là những đứa trẻ hư.)

Máy chủ được xây dựng để ông già Noel có thể nhanh chóng kiểm tra danh sách của mình khi đang di chuyển. Sau khi người dùng kết nối với máy chủ, nó sẽ nhắc họ nhập danh sách $N$ số nguyên $H(1), H(2), \dots, H(N)$ mã hóa hoán vị $H$, xác minh danh sách này có đúng hay không, và sau đó giải mã danh sách bí mật của ông già Noel. Qua nhiều tháng nghiên cứu, bạn đã tìm ra một lỗ hổng thời gian ở kênh bên (side-channel). Giả sử bạn nhập vào một hoán vị $Q$. Nếu $H = Q$, máy chủ sẽ cấp quyền truy cập ngay lập tức. Nếu không, hãy xem xét một đồ thị trên $N$ đỉnh, và thêm một cạnh từ mỗi đỉnh $i$ đến đỉnh $H(Q(i))$. Bạn đã phát hiện ra rằng thuật toán xác thực phức tạp của máy chủ sẽ mất chính xác số giây bằng với số thành phần liên thông trong đồ thị kết quả để phản hồi cho bạn thông báo lỗi Access Denied.

Ví dụ, giả sử $N = 4$ và hoán vị mật mã $H$ như sau:

Nếu bạn cố gắng đăng nhập vào máy chủ với đầu vào 4 3 2 1, vì hoán vị này không khớp với $H$ và vì đồ thị được mô tả ở trên có hai thành phần liên thông (một thành phần chứa chu trình các cạnh $1 \to 4 \to 2 \to 1$ và một thành phần khác chỉ chứa vòng lặp tự thân $3 \to 3$), máy chủ sẽ phản hồi thông báo lỗi Access Denied sau độ trễ 2 giây.

Lưu ý rằng nếu bạn cố gắng đăng nhập vào máy chủ nhiều lần với các đầu vào $Q$ khác nhau, nó sẽ xác thực $Q$ mỗi lần dựa trên cùng một $H$ đã lưu trữ. Nó không thay đổi $H$ theo bất kỳ cách nào để phản hồi lại các đầu vào của bạn.

Ông già Noel sẽ nhận thấy nếu máy chủ của ông ấy bị tấn công bởi các yêu cầu trái phép. Bạn đã ước tính rằng mình chỉ có thể thực hiện tối đa 1 510 lần thử đăng nhập trước khi gây ra quá nhiều nghi ngờ. Bạn có thể tìm ra một chiến lược hiệu quả để xác định hoán vị mật mã không?

Tương tác

Đây là một bài toán tương tác. Quá trình tương tác bắt đầu bằng việc đọc một số nguyên $N$ ($1 \le N \le 220$) từ đầu vào chuẩn, là số lượng chữ cái trong tiếng North-Polish. Giám khảo không thích nghi: hoán vị ẩn $H$ được chọn tại thời điểm này và sẽ không thay đổi trong suốt phần còn lại của quá trình tương tác.

Để thử đăng nhập vào máy chủ, hãy in một dòng với $N$ số nguyên cách nhau bởi dấu cách $Q(1), \dots, Q(N)$, trong đó $Q$ là một hoán vị của $\{1, 2, \dots, N\}$. Sau đó đọc một số nguyên duy nhất từ đầu vào chuẩn, là khoảng thời gian tính bằng giây để máy chủ phản hồi đầu vào của bạn.

Nếu độ trễ này là 0, bạn đã tìm thấy thành công hoán vị mật mã $H$ và chương trình của bạn nên kết thúc. Nếu không, độ trễ này là số lượng thành phần liên thông trong đồ thị được xây dựng theo quy trình mô tả ở trên.

Bạn có thể thử đăng nhập tối đa 1 510 lần. Nếu bạn hết số lần thử, chương trình của bạn nên thoát một cách sạch sẽ (mặc dù nó sẽ bị đánh giá là sai vì không giải mã được danh sách ngoan hay hư của ông già Noel).

Ghi chú

Đừng quên xóa bộ đệm đầu ra (flush) sau mỗi dòng bạn in và thoát sạch sẽ sau khi quá trình tương tác hoàn tất. Vui lòng đảm bảo rằng bạn tuân thủ chính xác giao thức tương tác ở trên liên quan đến thông tin nào cần in trên dòng đầu ra nào: ví dụ, nếu giao thức yêu cầu bạn in một danh sách các số nguyên cách nhau bởi dấu cách trên một dòng duy nhất, giám khảo sẽ không chấp nhận mỗi số nguyên trên dòng riêng của nó.

Nếu giám khảo nhận được đầu vào không hợp lệ hoặc không mong đợi, nó sẽ in -1 và sau đó thoát ngay lập tức. Chương trình của bạn phải phát hiện điều này và thoát sạch sẽ để nhận phán quyết Wrong Answer. Nếu chương trình của bạn bị chặn chờ đợi tương tác thêm từ giám khảo, hoặc cố gắng diễn giải -1 là số lượng thành phần, bạn có thể nhận được một phán quyết bị từ chối khác (chẳng hạn như Time Limit Exceeded hoặc Runtime Error) thay vì Wrong Answer.

Bạn đã được cung cấp một công cụ dòng lệnh để kiểm tra cục bộ. Công cụ này có các chú thích ở trên cùng giải thích cách sử dụng.

Ví dụ

Dữ liệu vào 1

3
1
2
0

Dữ liệu ra 1

1 2 3
2 1 3
3 1 2