Alice sống tại Vương quốc JOI và định mời Bob, người đang sống tại Cộng hòa IOI, đến chơi. Trước đó, cô muốn gửi cho Bob bản đồ đường bay của vương quốc. JOI là quốc đảo gồm \(N\) hòn đảo, đánh số từ \(0\) đến \(N-1\), với \(M\) đường bay hai chiều. Với \(0\le i<M\), đường bay thứ \(i+1\) nối đảo \(A_i\) và đảo \(B_i\). Không có hai đường bay nối cùng một cặp đảo.

Alice phải sử dụng máy điện báo đặc biệt của vương quốc. Máy cho phép gửi một đồ thị vô hướng, nhưng số hiệu các đỉnh và các cạnh sẽ bị xáo trộn ngẫu nhiên. Cụ thể, gọi \(G\) là đồ thị Alice gửi, có \(V\) đỉnh và \(U\) cạnh:

1. Alice chỉ định \(V\) và \(U\), đánh số các đỉnh từ \(0\) đến \(V-1\) và các cạnh từ \(0\) đến \(U-1\).
2. Alice chỉ định hai dãy \(C_0,\ldots,C_{U-1}\) và \(D_0,\ldots,D_{U-1}\). Cạnh số \(j\) nối đỉnh \(C_j\) với đỉnh \(D_j\).
3. Vương quốc tạo một hoán vị \(p[0],\ldots,p[V-1]\) của \(0,\ldots,V-1\) rồi thay mỗi \(C_j\) bằng \(p[C_j]\) và mỗi \(D_j\) bằng \(p[D_j]\).
4. Tiếp đó, vương quốc tạo một hoán vị \(q[0],\ldots,q[U-1]\) của \(0,\ldots,U-1\). Hai dãy được thay đồng thời bằng \(C_{q[0]},\ldots,C_{q[U-1]}\) và \(D_{q[0]},\ldots,D_{q[U-1]}\).
5. Bob nhận \(V\), \(U\) và hai dãy \(C\), \(D\) sau các phép thay thế trên.

Máy chỉ truyền được đơn đồ thị, tức đồ thị không có cạnh song song hoặc khuyên. Nói cách khác, với mọi \(0\le i<j<U\), phải có \((C_i,D_i)\ne(C_j,D_j)\) và \((C_i,D_i)\ne(D_j,C_j)\); đồng thời \(C_i\ne D_i\) với mọi \(0\le i<U\).

Alice muốn truyền bản đồ bằng đồ thị có ít đỉnh nhất. Hãy viết hai chương trình:

• Chương trình thứ nhất nhận \(N\), \(M\), \(A\), \(B\) và xuất thông tin đồ thị \(G\) mà Alice gửi.
• Chương trình thứ hai nhận thông tin đồ thị \(G\) mà Bob nhận được và khôi phục bản đồ đường bay ban đầu, bao gồm số hiệu các đảo.

Chi tiết cài đặt

Trên LQDOJ, bạn nộp một tệp C++ khai báo #include "airline.h" và cài đặt cả hai hàm Alice và Bob dưới đây. Trình chấm chạy hai bản sao tách biệt của chương trình, vì vậy hai hàm không thể trao đổi dữ liệu qua biến toàn cục.

Hàm phía Alice có chữ ký:

void Alice(int N, int M, int A[], int B[]);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu. N là số đảo, M là số đường bay; A và B là hai mảng độ dài \(M\) mô tả bản đồ. Hàm Alice dùng các hàm sau để xuất đồ thị:

void InitG(int V, int U);
void MakeG(int pos, int C, int D);

InitG chỉ định số đỉnh và số cạnh của \(G\):

• V phải là số nguyên từ \(1\) đến \(1500\), nếu không nhận Wrong Answer [1].
• U phải là số nguyên từ \(0\) đến \(V(V-1)/2\), nếu không nhận Wrong Answer [2].

MakeG chỉ định cạnh số pos, nối hai đỉnh C và D, với \(V\), \(U\) là các giá trị đã truyền cho InitG:

• pos phải thuộc \([0,U-1]\), nếu không nhận Wrong Answer [3].
• Không được gọi nhiều lần với cùng pos, nếu không nhận Wrong Answer [4].
• C và D phải thuộc \([0,V-1]\) và khác nhau, nếu không nhận Wrong Answer [5].

Trong Alice, phải gọi InitG đúng một lần, sau đó gọi MakeG đúng \(U\) lần:

• Gọi InitG lần thứ hai: Wrong Answer [6].
• Gọi MakeG trước InitG: Wrong Answer [7].
• Khi Alice kết thúc, chưa gọi InitG hoặc số lần gọi MakeG khác \(U\): Wrong Answer [8].
• Khi Alice kết thúc, đồ thị được mô tả không phải đơn đồ thị: Wrong Answer [9].

Nếu lần gọi Alice bị đánh giá sai, chương trình bị kết thúc ngay.

Hàm phía Bob có chữ ký:

void Bob(int V, int U, int C[], int D[]);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu. V, U là số đỉnh và số cạnh của đồ thị nhận được; C, D là hai mảng độ dài \(U\) mô tả các cạnh. Hàm Bob dùng các hàm sau để khôi phục và xuất bản đồ:

void InitMap(int N, int M);
void MakeMap(int A, int B);

InitMap chỉ định số đảo và số đường bay đã khôi phục:

• N phải bằng đúng số đảo ban đầu, nếu không nhận Wrong Answer [10].
• M phải bằng đúng số đường bay ban đầu, nếu không nhận Wrong Answer [11].

MakeMap chỉ định một đường bay nối đảo A và đảo B, với \(N\) là giá trị đã truyền cho InitMap:

• A và B phải thuộc \([0,N-1]\) và khác nhau, nếu không nhận Wrong Answer [12].
• Nếu bản đồ ban đầu không có đường bay nối hai đảo này, nhận Wrong Answer [13].
• Không được xuất lại đường bay đã xuất. Khi gọi MakeMap(A,B), nếu đã từng gọi MakeMap(A,B) hoặc MakeMap(B,A), nhận Wrong Answer [14].

Trong Bob, phải gọi InitMap đúng một lần, sau đó gọi MakeMap đúng \(M\) lần:

• Gọi InitMap lần thứ hai: Wrong Answer [15].
• Gọi MakeMap trước InitMap: Wrong Answer [16].
• Khi Bob kết thúc, chưa gọi InitMap hoặc số lần gọi MakeMap khác \(M\): Wrong Answer [17].

Nếu lần gọi Bob bị đánh giá sai, chương trình bị kết thúc ngay.

Quy trình chấm

1. Gọi Alice một lần với các tham số mô tả bản đồ ban đầu.
2. Xáo trộn số hiệu đỉnh và cạnh của đồ thị \(G\) mà Alice chỉ định, rồi gọi Bob một lần với đồ thị thu được.
3. Đánh giá chương trình. Nếu phát hiện câu trả lời sai, chương trình bị kết thúc ngay.

Lưu ý quan trọng

• Bạn có thể cài đặt các hàm nội bộ và dùng biến toàn cục. Tệp nộp được biên dịch cùng trình chấm. Nên đặt các biến toàn cục và hàm nội bộ trong namespace ẩn danh hoặc khai báo static để tránh xung đột tên.
• Khi chấm thật, chương trình chạy thành hai tiến trình riêng cho Alice và Bob. Hai tiến trình không thể dùng chung biến toàn cục.
• Chương trình không được dùng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Có thể ghi thông tin gỡ lỗi ra luồng lỗi chuẩn.

Header airline.h được cung cấp trong phần tệp đính kèm. Trình chấm thật chạy hai vai trò trong hai tiến trình riêng và khác với trình chấm mẫu một tiến trình của đề gốc.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa hai số nguyên \(N\), \(M\), cách nhau bởi dấu cách.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i+1\) (\(0\le i<M\)) chứa hai số nguyên \(A_i\), \(B_i\), cách nhau bởi dấu cách, mô tả một đường bay.

Dữ liệu ra

Trình chấm mẫu ghi kết quả ra đầu ra chuẩn theo định dạng sau:

• Nếu chương trình bị đánh giá sai, trình chấm mẫu ghi loại lỗi, chẳng hạn Wrong Answer [1], rồi kết thúc.
• Nếu cả hai lần gọi Alice và Bob đều không bị đánh giá sai, trình chấm mẫu ghi Accepted. và còn xuất giá trị \(V\).

Các thông báo không có dấu ngoặc kép. Nếu có nhiều loại lỗi, trình chấm mẫu chỉ thông báo một loại.

Ràng buộc

• \(1\le N\le 1\,000\).
• \(0\le M\le N(N-1)/2\).
• \(0\le A_i,B_i\le N-1\) và \(A_i\ne B_i\) với \(0\le i<M\).
• \((A_i,B_i)\ne(A_j,B_j)\) và \((A_i,B_i)\ne(B_j,A_j)\) với \(0\le i<j<M\).

Phân nhóm

1. \(22\) điểm tối đa: \(N\le 10\)
2. \(15\) điểm tối đa: \(N\le 40\)
3. \(63\) điểm tối đa: Không có

Trong nhóm 1 và nhóm 2, chương trình được toàn bộ điểm của nhóm nếu giải đúng tất cả bộ dữ liệu của nhóm.

Trong nhóm 3, nếu chương trình giải đúng tất cả bộ dữ liệu, gọi \(\mathrm{MaxDiff}\) là giá trị lớn nhất của \(V-N\) trên các bộ dữ liệu của nhóm. Điểm được tính như sau:

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

Ví dụ giao tiếp

4 3
0 1
0 2
0 3

Các lời gọi diễn ra theo thứ tự sau. Tất cả các hàm trong bảng đều không trả về giá trị.

Các tham số mà trình chấm truyền vào hai hàm là:

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

Nguồn

JOI 2017/2018 Spring Training Camp, Contest Day 3, đề tiếng Anh chính thức và đề tiếng Nhật chính thức.