Jian-Jia là một cậu bé yêu thích các trò chơi. Khi được hỏi, cậu thích chơi một trò chơi hơn là trả lời trực tiếp. Jian-Jia gặp cô bạn Mei-Yu và kể về mạng lưới chuyến bay ở Đài Loan. Đài Loan có \(n\) thành phố, được đánh số \(0, \ldots, n-1\); một số thành phố được nối với nhau bởi các chuyến bay. Mỗi chuyến bay nối hai thành phố và có thể đi theo cả hai chiều.

Mei-Yu hỏi liệu có thể đi giữa hai thành phố bất kỳ bằng máy bay, trực tiếp hoặc gián tiếp, hay không. Jian-Jia không muốn tiết lộ câu trả lời nên đề nghị chơi một trò chơi. Mei-Yu có thể đặt câu hỏi dạng “Hai thành phố \(x\) và \(y\) có chuyến bay trực tiếp nối với nhau không?”, và Jian-Jia sẽ trả lời ngay lập tức. Mei-Yu hỏi về mỗi cặp thành phố đúng một lần, với tổng số câu hỏi là

Mei-Yu thắng nếu sau khi nhận câu trả lời cho \(i\) câu hỏi đầu tiên, với một giá trị \(i < r\), cô có thể suy ra mạng có liên thông hay không, tức là có thể đi giữa mọi cặp thành phố bằng các chuyến bay, trực tiếp hoặc gián tiếp, hay không. Ngược lại, nếu cô cần hỏi đủ cả \(r\) câu, Jian-Jia thắng.

Để trò chơi thú vị hơn đối với Jian-Jia, hai bạn thỏa thuận rằng cậu có thể bỏ qua mạng lưới chuyến bay thực tế của Đài Loan và tự tạo ra mạng theo diễn biến trò chơi, lựa chọn câu trả lời dựa trên những câu hỏi trước đó của Mei-Yu. Nhiệm vụ của bạn là giúp Jian-Jia thắng bằng cách quyết định cậu nên trả lời các câu hỏi như thế nào.

Ví dụ

Ba ví dụ dưới đây minh họa luật chơi. Mỗi ví dụ có \(n=4\) thành phố và \(r=6\) lượt hỏi đáp. Trong các bảng, yes nghĩa là có chuyến bay trực tiếp, còn no nghĩa là không có.

Trong ví dụ thứ nhất, Jian-Jia thua: sau lượt 4, Mei-Yu biết chắc có thể đi giữa hai thành phố bất kỳ bằng máy bay, bất kể Jian-Jia trả lời câu 5 và câu 6 ra sao.

Lượt   Câu hỏi   Trả lời
1      0, 1      yes
2      3, 0      yes
3      1, 2      no
4      0, 2      yes
-----  --------  ------
5      3, 1      no
6      2, 3      no

Trong ví dụ thứ hai, sau lượt 3, Mei-Yu có thể chứng minh rằng không thể đi giữa hai thành phố 0 và 1 bằng máy bay, bất kể Jian-Jia trả lời câu 4, 5 và 6 ra sao. Vì vậy, Jian-Jia lại thua.

Lượt   Câu hỏi   Trả lời
1      0, 3      no
2      2, 0      no
3      0, 1      no
-----  --------  ------
4      1, 2      yes
5      1, 3      yes
6      2, 3      yes

Trong ví dụ cuối, Mei-Yu không thể xác định liệu có thể đi giữa hai thành phố bất kỳ bằng máy bay hay không cho đến khi cả sáu câu hỏi đều được trả lời, nên Jian-Jia thắng. Cụ thể, vì Jian-Jia trả lời yes cho câu cuối trong bảng dưới đây nên có thể đi giữa mọi cặp thành phố. Nếu cậu trả lời no cho câu cuối thì điều đó không thể thực hiện được.

Lượt   Câu hỏi   Trả lời
1      0, 3      no
2      1, 0      yes
3      0, 2      no
4      3, 1      yes
5      1, 2      no
6      2, 3      yes

Nhiệm vụ

Hãy viết chương trình giúp Jian-Jia thắng trò chơi. Cả Mei-Yu lẫn Jian-Jia đều không biết chiến lược của người kia. Mei-Yu có thể hỏi các cặp thành phố theo thứ tự bất kỳ; Jian-Jia phải trả lời ngay lập tức và không biết trước các câu hỏi tiếp theo. Bạn cần cài đặt hai hàm:

• initialize(n): được gọi đầu tiên; n là số thành phố.
• hasEdge(u, v): sau đó được gọi \(r=n(n-1)/2\) lần, tương ứng với các câu hỏi của Mei-Yu theo đúng thứ tự cô hỏi. Bạn phải trả lời có chuyến bay trực tiếp giữa hai thành phố \(u\) và \(v\) hay không. Trả về 1 nếu có, 0 nếu không.

Các subtasks

Mỗi subtask gồm nhiều ván chơi. Bạn chỉ được điểm của một subtask nếu chương trình giúp Jian-Jia thắng tất cả các ván của subtask đó.

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên game.c, game.cpp hoặc game.pas, cài đặt các chương trình con theo đặc tả trên và chữ ký dưới đây.

C/C++:

void initialize(int n);
int hasEdge(int u, int v);

Pascal:

procedure initialize(n: longint);
function hasEdge(u, v: longint): longint;

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng 1: n.
• \(r\) dòng tiếp theo: mỗi dòng chứa hai số nguyên u và v, mô tả một câu hỏi về hai thành phố \(u\) và \(v\).