Anna sống tại quần đảo IOI và mời người bạn Bruno đến chơi. Quần đảo gồm \(N\) đảo, được đánh số từ \(1\) đến \(N\), và \(N-1\) cây cầu, được đánh số từ \(0\) đến \(N-2\). Cầu \(i\) nối hai chiều đảo \(A[i]\) và đảo \(B[i]\). Có thể đi giữa hai đảo bất kỳ qua các cây cầu.

Nhà Anna nằm trên đảo \(T\), nhưng Bruno không biết số hiệu đảo này. Để giúp Bruno, Anna sẽ cắm trên mỗi đảo đúng một lá cờ ghi một số nguyên. Anna không biết Bruno sẽ cập bến ở đảo nào.

Bruno cập bến tại đảo \(S\). Anh chỉ được biết:

• số hiệu \(S\) và số ghi trên lá cờ tại đảo \(S\);
• số hiệu của tất cả các đảo nối trực tiếp với \(S\) và số ghi trên cờ tại các đảo đó.

Bruno phải đi từ \(S\) đến \(T\) theo đường dùng ít cầu nhất. Dựa chỉ trên thông tin được cung cấp, Bruno phải xác định \(S\) có phải đảo \(T\) hay không; nếu không, anh phải chọn đúng đảo tiếp theo trên đường đi ngắn nhất duy nhất đến \(T\).

Yêu cầu

Cài đặt chiến lược đặt cờ của Anna và chiến lược chọn hành động tiếp theo của Bruno.

Giao diện nộp bài

Nộp một tệp C++ có chứa hai hàm sau:

#include "navigation.h"

void Anna(int K, int N, int T, int A[], int B[]);
void Bruno(int K, int S, int F, int L, int P[], int Q[]);

Tệp navigation.h cung cấp hai hàm hệ thống:

void Flag(int I, int V);
void Answer(int X);

Hệ thống liên kết cùng mã nguồn thí sinh thành hai tiến trình độc lập: một tiến trình chỉ gọi Anna, tiến trình còn lại chỉ gọi Bruno. Hai tiến trình không chia sẻ biến toàn cục hay trạng thái bộ nhớ.

Hàm Anna

void Anna(int K, int N, int T, int A[], int B[]);

Hàm được gọi đúng một lần:

• K là số hiệu nhóm chấm.
• N là số đảo.
• T là đảo có nhà Anna.
• A và B là hai mảng dài \(N-1\); cầu \(i\) nối A[i] với B[i], với \(0 \le i \le N-2\).

Trong Anna, phải gọi:

void Flag(int I, int V);

để đặt cờ. Các lời gọi phải thỏa mãn:

• \(1 \le I \le N\); nếu không, kết quả là Wrong Answer [1].
• Không được gọi hai lần với cùng I; nếu không, kết quả là Wrong Answer [2].
• \(0 \le V \le N\); nếu không, kết quả là Wrong Answer [3].
• Phải gọi đúng \(N\) lần, tức đúng một lần cho mỗi đảo; nếu không, kết quả là Wrong Answer [4].

Hàm Bruno

void Bruno(int K, int S, int F, int L, int P[], int Q[]);

Hàm được gọi đúng một lần, trong một tiến trình mới, sau khi hệ thống hoàn tất việc chạy Anna:

• K là số hiệu nhóm chấm.
• S là đảo Bruno cập bến.
• F là số ghi trên cờ tại đảo \(S\).
• L là số đảo nối trực tiếp với \(S\).
• P là mảng dài \(L\) chứa số hiệu các đảo kề \(S\).
• Q là mảng dài \(L\); Q[j] là số ghi trên cờ ở đảo P[j], với \(0 \le j < L\).

Trong Bruno, phải gọi đúng một lần:

void Answer(int X);

• Nếu \(S=T\), phải trả lời X = S.
• Nếu \(S \ne T\), X phải là đảo kề \(S\) nằm trên đường đi ngắn nhất duy nhất từ \(S\) đến \(T\).
• X phải bằng S hoặc là một phần tử của P; nếu không, kết quả là Wrong Answer [5].
• Gọi Answer từ hai lần trở lên cho kết quả Wrong Answer [6].
• Không gọi Answer cho kết quả Wrong Answer [7].
• Nếu \(S=T\) nhưng X != T, kết quả là Wrong Answer [8].
• Nếu \(S \ne T\) nhưng chọn sai đảo tiếp theo, kết quả là Wrong Answer [9].

Bài nộp không được đọc hoặc ghi dữ liệu qua đầu vào chuẩn, đầu ra chuẩn hay bất kỳ tệp nào.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le S,T \le N\).
• \(1 \le A[i],B[i] \le N\) với mọi \(0 \le i \le N-2\).
• \(1 \le K \le 4\).
• Có thể đi giữa mọi cặp đảo bằng các cây cầu.

Phân nhóm

• Nhóm 1 (10 điểm): \(K=1\)
• Nhóm 2 (15 điểm): \(K=2\); mọi giá trị V truyền cho Flag phải thuộc \([0,2]\)
• Nhóm 3 (20 điểm): \(K=3\); mọi V thuộc \(\{0,1\}\); không có đảo nào có đúng hai đảo kề; \(S \ne T\)
• Nhóm 4 (55 điểm): \(K=4\); mọi V thuộc \(\{0,1\}\)

Ví dụ

5 3 2 1
1 3
3 2
3 4
4 5
2

Accepted : V_max = 1

Anna(1, 5, 2, {1, 3, 3, 4}, {3, 2, 4, 5})
Flag(1, 1)
Flag(2, 1)
Flag(3, 0)
Flag(4, 0)
Flag(5, 1)

Bruno(1, 3, 0, 3, {2, 1, 4}, {1, 1, 0})
Answer(2)