JOI-kun và em gái IOI-chan đang chơi tại công viên JOIOI. Công viên có \(N\) trò chơi, đánh số từ \(0\) đến \(N-1\), và \(M\) đường đi hai chiều. Mỗi đường nối hai trò chơi khác nhau; từ mọi trò chơi đều có thể đi đến mọi trò chơi khác.

Mỗi trò chơi có một bảng tin, trên đó JOI-kun được ghi đúng một số \(0\) hoặc \(1\). Nội dung đã ghi không bị khách khác thay đổi. Hai người sẽ chơi riêng rồi gặp lại. Không có thiết bị liên lạc, JOI-kun muốn truyền cho IOI-chan số nguyên \(X\) biểu diễn thời gian gặp mặt:

1. JOI-kun ghi \(0\) hoặc \(1\) lên bảng tin của mọi trò chơi.
2. IOI-chan bắt đầu tại một trò chơi, đọc bảng tin ở đó, rồi có thể đi qua các đường và đọc bảng tin tại mỗi nơi cô đến.

Hãy viết hai chương trình để IOI-chan xác định đúng \(X\) với ít lần di chuyển. Hai chương trình nhận cùng một đồ thị, gồm cùng số hiệu đỉnh và cùng thứ tự các cạnh.

Yêu cầu cài đặt

Bạn cần cài đặt hai hàm sau trong cùng bài nộp:

void Joi(int N, int M, int A[], int B[], long long X, int T);
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T);

Mỗi hàm được gọi đúng một lần cho mỗi bộ kiểm thử.

Trong cả hai hàm, \(N,M\) là số trò chơi và số đường; cạnh thứ \(i\) nối \(A[i]\) với \(B[i]\) (\(0\le i<M\)); \(T\) là số hiệu nhóm. Với Joi, \(X\) là số cần truyền. Với Ioi, \(P\) là trò chơi ban đầu và \(V\) là giá trị trên bảng tin tại \(P\).

Trong Joi, gọi:

void MessageBoard(int attr, int msg);

để ghi msg lên bảng tại attr.

• Phải có \(0\le attr<N\); nếu không, nhận Wrong Answer[1].
• Không được gọi hai lần với cùng attr; nếu vi phạm, nhận Wrong Answer[2].
• msg phải bằng \(0\) hoặc \(1\); nếu không, nhận Wrong Answer[3].
• Phải gọi MessageBoard đúng \(N\) lần; nếu không, nhận Wrong Answer[4].
• Một lời gọi không hợp lệ khiến tiến trình Joi dừng ngay.

Trong Ioi, gọi:

int Move(int dest);

để di chuyển tới dest; hàm trả về giá trị trên bảng tin tại đó.

• Phải có \(0\le dest<N\); nếu không, nhận Wrong Answer[6].
• dest phải kề vị trí hiện tại; nếu không, nhận Wrong Answer[7].
• Không được gọi Move quá \(20\,000\) lần; nếu vi phạm, nhận Wrong Answer[8].
• Ioi phải trả về đúng \(X\); nếu không, nhận Wrong Answer[5].

Bạn có thể khai báo hàm phụ và biến toàn cục, nhưng mọi hàm/biến nội bộ nên được khai báo static để tránh xung đột tên. Khi chấm chính thức, Joi và Ioi chạy trong hai tiến trình riêng biệt, vì vậy không thể chia sẻ biến toàn cục. Không được đọc/ghi luồng chuẩn hoặc dùng tệp hay phương thức khác để liên lạc.

Định dạng bộ chấm mẫu

Bộ chấm mẫu đọc:

• Dòng đầu chứa \(N,M,X,P,T\).
• \(M\) dòng tiếp theo, dòng thứ \(i+1\) chứa \(A[i],B[i]\).

Nếu đúng, bộ chấm mẫu in Accepted : #move=12345, trong đó số cuối là số lần gọi Move. Nếu sai, nó in Wrong Answer [k]. Nếu có nhiều lỗi, chỉ một lỗi được báo. Bộ chấm mẫu chạy trong một tiến trình và khác bộ chấm chính thức; chương trình không được dựa vào sự khác biệt này.

Ràng buộc

• \(60\le N\le 10\,000\).
• \(1\le M\le 20\,000\).
• \(0\le A[i],B[i]<N\) và \(A[i]\ne B[i]\).
• Không có hai cạnh trùng nhau, kể cả khi đảo thứ tự hai đầu mút.
• Đồ thị liên thông.
• \(0\le X\le 2^{60}-1\).
• \(0\le P<N\).

Phân nhóm

• Nhóm 1 (8 điểm): \(T=1\), \(N\le 300\).
• Nhóm 2 (10 điểm): \(T=2\).
• Nhóm 3 (10 điểm): \(T=3\), \(M=N-1\), \(A[i]=i\), \(B[i]=i+1\) với \(0\le i\le N-2\), và gọi Move không quá \(250\) lần.
• Nhóm 4 (55 điểm): \(T=4\), \(N\ge 240\). Gọi \(C\) là số lần gọi Move lớn nhất trên mọi bộ kiểm thử của nhóm. Điểm nhóm là

Khi \(C>960\), hệ thống chính thức có thể hiển thị Correct : 0 point hoặc Incorrect.

• Nhóm 5 (17 điểm): \(T=5\) và gọi Move không quá \(120\) lần.

Ví dụ giao tiếp

PDF chỉ hiển thị phần đầu của ví dụ vì dữ liệu đầy đủ khá dài. Tệp sample-01.txt đầy đủ nằm trong tệp đính kèm chính thức.

60 59 123 5 1
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
...

Nguồn

JOI 2016/2017 Open Contest.