Bạn có biết công ty Just Ordinary Inventions không? Công việc của công ty này là thực hiện “những phát minh bình thường”.

JOI 君 đang chơi trò chơi mới nhất do công ty Just Ordinary Inventions phát triển.

Đây là trò chơi khám phá một hầm ngục gồm một số căn phòng và một số con đường. Mỗi con đường nối hai phòng khác nhau trong hầm ngục và có thể đi theo cả hai chiều. Giữa hai phòng khác nhau bất kỳ có nhiều nhất một con đường nối chúng, và không có con đường nào có hai đầu là cùng một phòng. Ngoài ra, có thể đi giữa hai phòng bất kỳ trong hầm ngục bằng một số con đường. Các phòng trông rất giống nhau; chỉ nhìn hình dáng của phòng thì hoàn toàn không thể phân biệt các phòng có cùng số đường đi ra.

Trong trò chơi này, mỗi phòng có một dấu mốc và một bệ để hỗ trợ người chơi. Dựa vào dấu mốc, có thể đánh số các con đường đi ra khỏi phòng là đường thứ nhất, thứ hai, v.v. Cấu trúc hầm ngục không thay đổi trong quá trình chơi. Vì vậy, nếu đi theo con đường có cùng số thứ tự từ cùng một phòng, bạn luôn đến cùng một phòng. Trên bệ có một viên ngọc mà người chơi có thể đổi màu. Màu ngọc là một trong các màu $1,2,\ldots,X$; khi bắt đầu trò chơi, ngọc ở tất cả các phòng đều có màu $1$. Màu ngọc không thay đổi trừ khi người chơi tác động.

JOI 君 nhận ra rằng nếu biết cấu trúc hầm ngục, tức là biết các phòng được nối với nhau bằng đường như thế nào, thì có thể dễ dàng hoàn thành trò chơi. Tuy nhiên, dù thử nhiều cách, JOI 君 vẫn không xác định được cấu trúc hầm ngục. Vì vậy, bạn quyết định viết chương trình xác định cấu trúc hầm ngục thay cho JOI 君.

Nhiệm vụ

Hãy viết chương trình khám phá hầm ngục và xác định cấu trúc của nó. Tuy nhiên, JOI 君 không muốn cấu trúc hầm ngục bị tiết lộ hoàn toàn. Vì vậy, thay vì trả lời trực tiếp cấu trúc hầm ngục, với mỗi số nguyên $i$ từ $1$ đến $R$, chương trình phải trả lời “có bao nhiêu cặp phòng mà số đường ít nhất cần đi qua để đi giữa chúng là đúng $i$” (hai cặp chỉ khác nhau ở thứ tự các phòng được xem là cùng một cặp).

Để khám phá hầm ngục, bạn được cung cấp thư viện thực hiện các hành động sau.

• Biết có bao nhiêu con đường đi ra khỏi phòng hiện tại.
• Biết màu của viên ngọc trên bệ trong phòng hiện tại.
• Đổi màu viên ngọc trên bệ trong phòng hiện tại thành màu được chỉ định (có thể chỉ định chính màu hiện tại). Sau đó, chọn một con đường đi ra khỏi phòng và đi theo đường đó sang phòng khác.
• Biết con đường vừa đi là đường thứ mấy trong các đường đi ra khỏi phòng hiện tại.

Chi tiết cài đặt

Bạn phải viết một chương trình cài đặt cách trả lời cho JOI 君. Chương trình phải bao gồm dungeon2.h.

Chương trình phải cài đặt thủ tục sau.

• void Inspect(int R)

  Thủ tục này được gọi đúng một lần khi bắt đầu.

  • Đối số R có nghĩa là, với mỗi số nguyên $i$ từ $1$ đến $R$, bạn phải trả lời số cặp phòng mà số đường ít nhất cần đi qua để đi giữa chúng là đúng $i$ (đổi thứ tự hai phòng vẫn được xem là cùng một cặp).

Ngoài ra, bạn phải gọi thủ tục sau để trả lời câu hỏi.

• void Answer(int D, int A)

  • Đối số D và A có nghĩa là trong lần gọi này, bạn trả lời rằng “có $A$ cặp phòng mà số đường ít nhất cần đi qua để đi giữa chúng là đúng $D$”.

  Các lần gọi Answer phải thỏa mãn các điều kiện sau.

  • D phải là số nguyên từ $1$ đến $R$. Nếu không, kết quả là Sai đáp án [1].
  • Không được gọi Answer từ hai lần trở lên với cùng đối số D. Nếu không, kết quả là Sai đáp án [2].
  • Phải gọi Answer đúng $R$ lần. Nếu không, kết quả là Sai đáp án [3].
  • A phải là số cặp phòng mà số đường ít nhất cần đi qua để đi giữa chúng là đúng $D$. Nếu không, kết quả là Sai đáp án [4].

  Nếu một lần gọi Answer bị đánh giá là sai đáp án, phần còn lại của chương trình không được đảm bảo sẽ tiếp tục chạy.

Ngoài ra, chương trình có thể gọi các thủ tục sau.

• void Move(int I, int C)

  • Đối số I là số thứ tự của con đường mà người chơi chọn để di chuyển. Ngay sau lần gọi này, người chơi đi theo con đường thứ $I$ đi ra khỏi phòng hiện tại để sang phòng khác.
  • Đối số C chỉ định rằng trước khi di chuyển, màu viên ngọc trên bệ trong phòng hiện tại được đổi thành màu $C$.

  Các lần gọi Move phải thỏa mãn các điều kiện sau.

  • Gọi $K$ là số đường đi ra khỏi phòng hiện tại. Đối số I phải là số nguyên từ $1$ đến $K$. Nếu không, kết quả là Sai đáp án [5].
  • Gọi $X$ là số loại màu ngọc. Đối số C phải là số nguyên từ $1$ đến $X$. Giá trị $X$ được xác định theo từng nhiệm vụ con. Nếu không thỏa mãn, kết quả là Sai đáp án [6].
  • Không được gọi Move quá $1\,500\,000$ lần. Nếu vượt quá, kết quả là Sai đáp án [7].

• int NumberOfRoads()

  • Hàm này trả về số đường đi ra khỏi phòng hiện tại của người chơi.

• int LastRoad()

  • Hàm này trả về số thứ tự của con đường người chơi vừa đi trong các đường đi ra khỏi phòng hiện tại. Tuy nhiên, nếu gọi hàm này trước khi gọi Move lần nào, hàm trả về -1.

• int Color()

  • Hàm này trả về màu của viên ngọc trên bệ trong phòng hiện tại của người chơi.

Sau khi thủ tục Inspect được gọi, đáp án sẽ được chấm.

Bạn được phép cài đặt các thủ tục khác để sử dụng nội bộ hoặc khai báo biến toàn cục. Tuy nhiên, bài nộp của bạn không được trao đổi với đầu vào chuẩn, đầu ra chuẩn hay bất kỳ tệp nào khác bằng bất kỳ cách nào.

Biên dịch và chạy

Một trình chấm mẫu để kiểm thử chương trình được cung cấp trong tệp nén có thể tải từ trang web cuộc thi. Tệp nén này cũng chứa tệp mẫu mà bạn phải nộp.

Trình chấm mẫu gồm một tệp, là grader.c hoặc grader.cpp. Để kiểm thử chương trình, chạy các lệnh sau.

• Với C

  gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• Với C++

  g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

Nếu biên dịch thành công, một tệp thực thi tên grader được tạo ra.

Lưu ý rằng trình chấm thực tế khác với trình chấm mẫu. Trình chấm mẫu chạy dưới dạng một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào của trình chấm mẫu

Trình chấm mẫu đọc các dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu chứa các số nguyên $N,X,R$ cách nhau bởi dấu cách. Điều này có nghĩa là hầm ngục có $N$ phòng, từ phòng $1$, phòng $2$, $\ldots$, phòng $N$; có $X$ loại màu ngọc; và chương trình phải trả lời $R$ giá trị.
• Trong $2N$ dòng tiếp theo, dòng thứ $2i-1$ ($1 \le i \le N$) chứa số nguyên $D_i$, biểu thị có $D_i$ đường đi ra khỏi phòng $i$. Dòng thứ $2i$ ($1 \le i \le N$) chứa $D_i$ số nguyên $T_{i1},T_{i2},\ldots,T_{iD_i}$ cách nhau bởi dấu cách. Điều này có nghĩa là đi theo con đường thứ $j$ ($1 \le j \le D_i$) từ phòng $i$ sẽ đến phòng $T_{ij}$.
• Dòng thứ $j$ trong $R$ dòng tiếp theo ($1 \le j \le R$) chứa số nguyên $A_j$. Điều này có nghĩa là có $A_j$ cặp phòng mà số đường ít nhất cần đi qua để đi giữa chúng là đúng $j$. Tức là, với mỗi $j$ ($1 \le j \le R$), trình chấm mẫu đánh giá là đúng khi gọi Answer với đối số D bằng $j$ và đối số A bằng $A_j$, và đánh giá là sai trong các trường hợp khác.

Trình chấm mẫu gọi thủ tục bạn đã viết với vị trí ban đầu của người chơi là phòng $1$.

Dữ liệu ra của trình chấm mẫu

Nếu chương trình kết thúc bình thường, trình chấm mẫu in thông tin sau trên một dòng ra đầu ra chuẩn (dấu ngoặc kép không thực sự được in).

• Nếu đúng, số lần gọi hàm Move được in dưới dạng như Accepted : #move = 8.
• Nếu sai, loại sai đáp án được in dưới dạng như Wrong Answer [1].

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau. Về ý nghĩa của $N,D_i,T_{ij}$, hãy xem mục “Dữ liệu vào của trình chấm mẫu”.

• $2 \le N \le 200$.
• $3 \le X \le 100$.
• $1 \le R \le 200$.
• $1 \le D_i \le N-1$ ($1 \le i \le N$).
• $1 \le T_{ij} \le N$ và $T_{ij} \ne i$ ($1 \le i \le N$, $1 \le j \le D_i$).
• $T_{i1},T_{i2},\ldots,T_{iD_i}$ ($1 \le i \le N$) đôi một khác nhau.
• Với mỗi $i,j$ ($1 \le i \le N$, $1 \le j \le D_i$), tồn tại $k$ ($1 \le k \le D_{T_{ij}}$) thỏa mãn $T_{T_{ij}k}=i$.
• Có thể đi giữa hai phòng bất kỳ bằng một số con đường.

Nhiệm vụ con

Dưới đây, gọi số phòng của hầm ngục trong dữ liệu vào là $N$ và số đường là $M$.

Nhiệm vụ con 1 [17 điểm]

Thỏa mãn các điều kiện sau.

• $N \le 50$.
• $M \le 100$.
• $X=100$.

Nhiệm vụ con 2 [27 điểm]

Thỏa mãn các điều kiện sau.

• $N \le 50$.
• $M \le 100$.
• $X=3$.

Nhiệm vụ con 3 [56 điểm]

• Thỏa mãn $X=3$.

Điểm của nhiệm vụ con này được xác định như sau.

• Gọi $L$ là giá trị lớn nhất của đại lượng sau trên tất cả các trường hợp kiểm thử của nhiệm vụ con này.

  • $\frac{C}{M}$, trong đó $C$ là số lần gọi Move.

• Khi đó, điểm của nhiệm vụ con này là:

  • 56 điểm nếu $L \le 14$.
  • $\lfloor 70-L\rfloor$ điểm nếu $14<L \le 32$.
  • $\left\lfloor 54-\frac{L}{2}\right\rfloor$ điểm nếu $32<L \le 64$.
  • 0 điểm nếu $64<L$.

Ở đây, $\lfloor x\rfloor$ là số nguyên lớn nhất không vượt quá $x$.

Trong hệ thống chấm, khi chương trình kết thúc đúng cách và được đánh giá là đúng, cột chi tiết sẽ hiển thị Accepted. Tuy nhiên, lưu ý rằng khi chấm nhiệm vụ con 3, với trường hợp kiểm thử có $C,M$ ở trên thỏa mãn $64<\frac{C}{M}$, cột kết quả sẽ hiển thị sai đáp án.

Ví dụ giao tiếp

Dưới đây là ví dụ dữ liệu vào được trình chấm mẫu đọc và các lần gọi thủ tục tương ứng.

Dữ liệu vào 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Các lần gọi thủ tục

Inspect(3)
NumberOfRoads() -> 1
LastRoad() -> -1
Move(1,2)
Color() -> 1
LastRoad() -> 1
NumberOfRoads() -> 3
Move(1,3)
Color() -> 2
Answer(1,4)
Answer(2,2)
Answer(3,0)

Lưu ý rằng các lần gọi hàm trong ví dụ này không nhất thiết đều có ý nghĩa.