Có ~n~ bạn đang chơi trên một đồ thị liên thông, vô hướng, có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Trọng số của các cạnh phân biệt đôi một.

Trên mỗi đỉnh của đồ thị có một người chơi đang cầm súng nước. Mỗi người chơi sẽ bắn súng nước vào người chơi ở gần người chơi đó nhất (với mỗi người chơi thì luôn có ít nhất một cạnh nối tới người đó). Người không bị ai bắn nước vào (nếu có) sẽ dành chiến thắng.

Bạn là ~1~ trong ~n~ người chơi, tuy nhiên bạn chỉ biết ~n~.

Bạn được hỏi các câu hỏi có dạng sau: ~S\ W~

• ~S~ là một tập con không rỗng của tập ~\{1, 2, ..., n\}~

• ~W~ là một số nguyên dương không vượt quá ~3 \cdot 10^6~.

Máy sẽ trả về ~1~ nếu tồn tại 2 đỉnh ~u, v \in S~ thỏa mãn có một cạnh nối giữa chúng với trọng số ~\leq w~ và ~0~ nếu không tồn tại 2 đỉnh như vậy.

Các bạn cần tìm đỉnh đảm bảo mình chiến thắng (nếu có) hoặc ~-1~ nếu không tồn tại một đỉnh nào như vậy

Implementation

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

int play(int n)

• Tham số ~n~ là số người chơi (cũng như số đỉnh của đồ thị)

• Hàm cần trả về một số nguyên là chỉ số đỉnh đảm bảo giành chiến thắng (hoặc ~-1~ nếu không tồn tại)

Thí sinh được phép gọi hàm sau:

int ask(vector<int> S, int W)

Hàm sẽ trả về ~1~ nếu tồn tại 2 đỉnh ~u, v \in S~ thỏa mãn có một cạnh nối giữa chúng với trọng số ~\leq w~ và ~0~ nếu không tồn tại 2 đỉnh như vậy.

Lưu ý: Thí sinh cần phải khai báo thư viện bằng dòng lệnh #include "gungame.h" ở đầu chương trình. Thí sinh được phép khai báo thêm hàm và biến bên ngoài, nhưng không được khai báo hàm tên là main.

Scoring

Gọi ~d~ là số lần bạn hỏi trong một test, ~D = max(d)~ với mọi test trong một subtask và ~T~ là điểm của subtask đó, điểm của bạn sẽ được tính như sau:

Sample grader

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

• Trình chấm mẫu đọc dữ liệu theo định dạng:
  • ~N\ M~
  • dòng ~1+i~ (~1\le i\le M~): ~U[i]\ V[i]\ W[i]~ thể hiện các cạnh của đồ thị
• Trình chấm mẫu in ra theo định dạng:
  • Kết quả hàm play
  • Số truy vấn ask đã dùng