Alice và Bob tham gia một trò chơi trên mê cung. Mê cung có ~N~ phòng, mỗi phòng có dạng hình tam giác, có thể di chuyển từ phòng này đến phòng khác nếu chúng có cạnh chung. Mê cung đảm bảo có thể di chuyển từ phòng này đến phòng khác bằng cách di chuyển qua một tập các phòng không lặp lại và có đúng một cách di chuyển thỏa mãn. Mỗi phòng có một bóng đèn ban đầu có trạng thái bật hoặc tắt. Trò chơi được diễn ra như sau:

Ở lượt đầu tiên, Alice bị quản trò bịt mắt và xuất hiện ở một phòng nào đó. Sau khi bỏ bịt mắt, cô sẽ chôn kho báu tại phòng đó, sau đó thực hiện liên tục các hành động. Quá trình ở lượt đầu tiên của Alice có thể được mô tả như sau:

• Khi Alice đến phòng chưa đến bao giờ, Alice sẽ đánh dấu phòng đó bằng một số ~x~ là số nguyên dương nhỏ nhất mà cô chưa dùng để đánh dấu. Lưu ý: Ở phòng mà Alice xuất hiện đầu tiên, cô sẽ luôn đánh dấu số ~1~ tại phòng đó.

• Tại một phòng, Alice có thể biết được:

  • Trạng thái đánh dấu của các phòng kề với phòng đang ở (chưa đánh dấu hoặc đã được đánh dấu một số nào đó).

  • Trạng thái của bóng đèn tại phòng đang ở (bật hoặc tắt).

• Trong suốt quá trình chơi, Alice có thể thực hiện một trong hai loại hành động như sau:

  • Di chuyển qua một phòng kề với phòng đang ở.

  • Thay đổi trạng thái của bóng đèn tại phòng đang ở (từ bật sang tắt hoặc ngược lại).

• Khi không còn thực hiện hành động nữa, Alice thoát khỏi mê cung và kết thúc lượt chơi của cô.

Sau khi Alice thoát khỏi mê cung, quản trò sẽ xóa hết tất cả dấu vết di chuyển của Alice, nhưng sẽ không thay đổi trạng thái của các bóng đèn.

Ở lượt thứ hai, Bob bị quản trò bịt mắt và xuất hiện ở một phòng nào đó. Lưu ý: Phòng Bob xuất hiện ban đầu có thể khác so với phòng Alice xuất hiện ban đầu. Sau khi bỏ bịt mắt, Bob có thể thực hiện các hành động tương tự như Alice (được mô tả ở trên). Nhiệm vụ của Bob là tìm cách di chuyển sao cho ngay trước khi kết thúc lượt chơi của Bob, anh ấy xuất hiện tại phòng Alice chôn kho báu. Khi đó thì hai người chiến thắng.

Trước khi chơi, Alice và Bob không biết được bất kỳ thông tin gì về mê cung, nhưng họ được phép bàn bạc chiến thuật. Nhiệm vụ của họ là cần tìm ra chiến thuật tối ưu sao cho có thể thắng được trò chơi.

Chi tiết cài đặt

Thí sinh cần cài đặt hai hàm sau:

void solveAlice(vector<int> S)

void solveBob(vector<int> S)

• Trong một test, trình chấm sẽ thực hiện trò chơi một lần duy nhất.

• Hàm solveAlice() cần mô tả chiến thuật chơi của Alice, trong khi hàm solveBob() cần mô tả chiến thuật chơi của Bob.

• Trong mỗi hàm, vector<int> S là mảng mô tả trạng thái~^{\dagger}~ của phòng mà Alice/Bob xuất hiện ban đầu.

~\dagger~: Mảng ~S~ mô tả trạng thái của phòng bao gồm ~4~ phần tử, đánh số từ ~0~ đến ~3~. Trong đó:

• ~S_0~ mô tả trạng thái bóng đèn của phòng (~S_0=1~ nếu bóng đèn tại phòng đó bật và ~S_0=0~ trong trường hợp ngược lại).

• ~S_1,S_2,S_3~ mô tả trạng thái đánh dấu của các phòng kề với phòng đang ở tại các hướng:

  • ~S_i=-1~ (~1\le i\le 3~) nếu như không tồn tại phòng kề với phòng đang ở tại hướng thứ ~i~.

  • ~S_i=0~ nếu như phòng kề với phòng đang ở tại hướng thứ ~i~ chưa được đánh dấu.

  • ~S_i>0~ nếu như phòng kề với phòng đang ở tại hướng thứ ~i~ đã được đánh dấu số ~S_i~.

• Lưu ý: Do trong mê cung không xác định được phương hướng nên các giá trị ~S_1,S_2,S_3~ có thể bị đảo lại theo bất kỳ thứ tự nào.

Trong hàm solveAlice() và solveBob(), thí sinh được phép gọi các hàm sau (thí sinh cần khai báo trước thư viện treasurelib.h để có thể sử dụng các hàm này):

vector<int> move(int i)

• Hàm này tương ứng với việc người chơi (Alice hoặc Bob) thực hiện di chuyển sang phòng kề với phòng đang ở tại hướng ~i~. Cần phải đảm bảo ~1\le i\le 3~ và ~S_i\ne -1~ theo mảng trạng thái tại phòng đang ở.

• Sau khi gọi hàm này, trình chấm sẽ trả về cho thí sinh một vector<int> tương ứng với mảng trạng thái của phòng sau khi đã di chuyển đến đó.

• Trong mỗi lần gọi hàm solveAlice() hay solveBob(), hàm này được gọi tối đa ~5\times N~ lần.

void flip()

• Hàm này tương ứng với việc thay đổi trạng thái bóng đèn của phòng đang ở (từ bật sang tắt hoặc ngược lại).

Ngoài ra, thí sinh còn được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm main(). Hàm solveAlice() được gọi trước hàm solveBob() và hai hàm này được gọi trên hai chương trình hoàn toàn độc lập.

Ràng buộc

• ~1\le N\le 10^5~.

Trình chấm của bài này mang tính thích ứng. Điều này tương đương với việc trạng thái của các bóng đèn sẽ không được cố định trước mà có thể thay đổi tùy vào chiến thuật chơi của Alice và Bob. Tuy nhiên, trình chấm đảm bảo trong suốt quá trình chơi, nếu Alice hoặc Bob đã bước vào một căn phòng thì trạng thái của bóng đèn tại phòng đó sẽ cố định lại và chỉ có thể thay đổi bởi hành động của người chơi.

Scoring

Cách tính điểm

Giả sử mỗi test có tối đa ~1~ điểm. Nếu vị trí phòng cuối cùng của Bob sau khi hàm solveBob() được gọi không phải căn phòng có kho báu, bạn sẽ được ~0~ điểm cho toàn bộ test đó. Ngược lại, gọi ~Q~ là tổng số lần thay đổi trạng thái đèn của Alice và Bob trong suốt lượt chơi. Khi đó, điểm của bạn sẽ được tính theo công thức như sau:

• Nếu ~Q\ge 49~ thì bạn được ~0.25\times 0.9^{Q-49}~ điểm.

• Nếu ~33\le Q\le 48~ thì bạn được ~0.25+0.25 \times 0.7^{Q-33}~ điểm.

• Nếu ~25\le Q\le 32~ thì bạn được ~0.5 + 0.2 \times 0.6^{Q-25}~ điểm.

• Nếu ~18\le Q\le 24~ thì bạn được ~0.7 + 0.2 \times 0.7^{Q-18}~ điểm.

• Nếu ~Q\le 17~ thì bạn được ~1~ điểm.

Điểm của mỗi subtask là điểm thấp nhất của một test trong subtask đó nhân với số điểm tối đa của subtask.

Sample Grader

Tải trình chấm mẫu tại đây.

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

• Dòng ~1~: ~N~
• Dòng ~i+1~ (~1 \le i < N~): ~u_i~ ~v_i~ (~u_i~ và ~v_i~ là chỉ số của hai phòng tương ứng có cạnh chung, ~1 \le u_i, v_i \le N~)
• Dòng ~N+1~: ~a~ ~b~ (~a~ và ~b~ là vị trí xuất phát của Alice và Bob, ~1 \le a, b \le N~)

Lưu ý: Trình chấm mẫu không đọc trạng thái ban đầu của các bóng đèn. Thay vào đó, chúng sẽ được trình chấm sinh ngẫu nhiên.

Trình chấm mẫu sẽ in ra một trong các kết quả sau:

• Accepted! nếu vị trí phòng cuối cùng của Bob trước khi Bob kết thúc lượt chơi là căn phòng chứa kho báu.

• Wrong answer! nếu vị trí phòng cuối cùng của Bob trước khi Bob kết thúc lượt chơi không phải là căn phòng chứa kho báu.

• Invalid operation move! nếu như trong chương trình của bạn, hàm solveAlice() hay solveBob() gọi ra hàm move() không hợp lệ.

Notes

Dưới đây là hình minh họa cho mê cung mẫu được cung cấp cho thí sinh cùng với cách di chuyển của Alice và Bob: