Nhiều nơi ở Nga có tuyết rơi vào mùa đông. Nga có $N$ thành phố, được đánh số từ $0$ đến $N-1$, và $N-1$ con đường, được đánh số từ $0$ đến $N-2$. Đường $i$ ($0\le i\le N-2$) nối hai thành phố khác nhau $A_i,B_i$ ($0\le A_i<B_i\le N-1$) theo cả hai hướng. Có thể đi lại giữa hai thành phố khác nhau bất kỳ qua một số con đường.

Tình trạng tuyết rơi trên mỗi con đường thay đổi theo ngày. Vào bất kỳ ngày nào, mỗi con đường hoặc có tuyết rơi hoặc không có tuyết rơi. Tình trạng này không thay đổi trong cùng một ngày.

Anya và Boris làm việc tại sở giao thông của Nga. Anya thuộc bộ phận quản lý thông tin đường bộ, còn Boris thuộc bộ phận trả lời câu hỏi của người dân. Người dân hỏi số con đường có tuyết rơi ít nhất phải đi qua để di chuyển từ thủ đô, thành phố $0$, đến một thành phố khác. Thông thường, sau khi nhận câu hỏi, Boris trao đổi với Anya rồi trả lời người dân.

Sắp tới, Nga sẽ tổ chức giải vô địch lập trình thế giới kéo dài $Q$ ngày. Trong thời gian diễn ra giải, các đường truyền dự kiến sẽ bị quá tải, khiến Anya và Boris khó trao đổi trực tiếp. Vì vậy, họ quyết định trao đổi theo cách sau.

• Anya nhận thông tin tuyết rơi của ngày đó vào đầu ngày và gửi dữ liệu đến máy chủ trung gian.
• Khi Boris nhận được câu hỏi của người dân, anh trả lời bằng cách trao đổi với máy chủ trung gian.

Tuy nhiên, việc trao đổi giữa Anya và Boris có các giới hạn sau.

• Dung lượng máy chủ trung gian là $L=1\,000$ bit. Anya chỉ có thể lưu tối đa $L$ bit thông tin trên máy chủ.
• Toàn bộ dữ liệu lưu trên máy chủ trung gian được khởi tạo thành $0$ vào đầu mỗi ngày.
• Trong một lần trao đổi với máy chủ trung gian, Boris có thể đọc thông tin của một bit do anh chỉ định.
• Để trả lời mỗi câu hỏi, Boris được trao đổi với máy chủ trung gian tối đa 20 lần.

Là người quen của giám đốc sở giao thông, bạn được giao nghĩ ra chiến lược cho Anya và Boris.

Các nhãn trong sơ đồ: thông tin tuyết rơi, máy chủ trung gian có dung lượng $L$ bit, tối đa 20 bit cho mỗi câu hỏi, và người dân.

Nhiệm vụ

Hãy viết chương trình cài đặt chiến lược của Anya và Boris để trả lời chính xác câu hỏi của người dân.

Chi tiết cài đặt

Bạn phải nộp hai tệp viết bằng cùng một ngôn ngữ lập trình.

Tệp thứ nhất có tên Anya.c hoặc Anya.cpp. Tệp này cài đặt chiến lược của Anya và phải cài đặt hai hàm sau. Chương trình phải include Anyalib.h.

• void InitAnya(int N, int A[], int B[])

  Hàm này được gọi đúng một lần trong mỗi bộ kiểm thử.

  • Tham số N là số thành phố.
  • Các tham số A[], B[] là hai dãy dài $N-1$, mô tả kết nối của các con đường. Các phần tử A[i], B[i] ($0\le i\le N-2$) là các số nguyên cho biết đường $i$ nối hai chiều giữa thành phố A[i] và B[i], thỏa mãn $0\le\texttt{A[i]}<\texttt{B[i]}\le N-1$.

• void Anya(int C[])

  Hàm này được gọi $Q$ lần sau khi InitAnya được gọi. Hàm tương ứng với việc Anya quyết định dãy bit lưu trên máy chủ trung gian sau khi thông tin tuyết rơi được cập nhật vào đầu ngày.

  • Tham số C[] là dãy dài $N-1$ mô tả thông tin tuyết rơi trên các con đường. Phần tử C[i] ($0\le i\le N-2$) là số nguyên 0 hoặc 1, biểu diễn thông tin của đường $i$: C[i] = 1 nghĩa là đường $i$ có tuyết rơi, còn C[i] = 0 nghĩa là đường $i$ không có tuyết rơi.

  Trong hàm Anya, bạn có thể gọi hàm sau.

  • void Save(int place, int bit)

    Hàm này biểu diễn thao tác Anya lưu một bit trên máy chủ trung gian.

    • Tham số place chỉ vị trí ghi bit. place phải là số nguyên từ $0$ đến $L-1$. Nếu gọi với giá trị ngoài phạm vi này, chương trình nhận kết quả Wrong Answer [1]. Ngoài ra, trong mỗi lần gọi hàm Anya, không được gọi hàm này hai lần trở lên với cùng giá trị place. Nếu gọi hai lần với cùng giá trị, chương trình nhận kết quả Wrong Answer [2].
    • Tham số bit là số nguyên biểu diễn bit cần ghi, phải là 0 hoặc 1. Nếu gọi với giá trị khác, chương trình nhận kết quả Wrong Answer [3].

  Sau khi gọi Save, bit tại vị trí place trên máy chủ trung gian trở thành bit.

  Nếu lời gọi Save bị đánh giá là sai, chương trình kết thúc ngay lúc đó.

  Ngay trước mỗi lần gọi Anya, tất cả bit trên máy chủ trung gian luôn được khởi tạo thành 0. Nghĩa là khi Anya kết thúc, các vị trí không được ghi bởi Save vẫn chứa 0.

Tệp thứ hai có tên Boris.c hoặc Boris.cpp. Tệp này cài đặt chiến lược của Boris và phải cài đặt hai hàm sau. Chương trình phải include Borislib.h.

• void InitBoris(int N, int A[], int B[])

  Hàm này được gọi đúng một lần trong mỗi bộ kiểm thử.

  • Tham số N là số thành phố.
  • Các tham số A[], B[] là hai dãy dài $N-1$, mô tả kết nối của các con đường. Các phần tử A[i], B[i] ($0\le i\le N-2$) là các số nguyên cho biết đường $i$ nối hai chiều giữa thành phố A[i] và B[i], thỏa mãn $0\le\texttt{A[i]}<\texttt{B[i]}\le N-1$.

• int Boris(int city)

  Hàm này được gọi một số lần sau khi InitBoris được gọi. Hàm tương ứng với hành động của Boris khi trả lời câu hỏi của người dân.

  • Tham số city biểu diễn câu hỏi của người dân. city là số nguyên từ $1$ đến $N-1$. Người dân muốn biết số con đường có tuyết rơi ít nhất phải đi qua để di chuyển từ thành phố $0$ đến thành phố city.
  • Hàm Boris phải trả về một số nguyên từ $0$ đến $N-1$, là câu trả lời cho người dân. Nếu trả về số nguyên ngoài phạm vi này, chương trình nhận kết quả Wrong Answer [4]. Nếu câu trả lời không đúng, chương trình nhận kết quả Wrong Answer [7].

  Trong hàm Boris, bạn có thể gọi hàm sau.

  • int Ask(int place)

    Hàm này biểu diễn thao tác Boris đọc một bit từ máy chủ trung gian.

    • Tham số place chỉ vị trí đọc bit. place phải là số nguyên từ $0$ đến $L-1$. Nếu gọi với giá trị ngoài phạm vi này, chương trình nhận kết quả Wrong Answer [5].

    Giá trị trả về của Ask là số nguyên 0 hoặc 1, biểu diễn nội dung bit tại vị trí place trên máy chủ trung gian. Ngoài ra, trong mỗi lần gọi Boris, chỉ được gọi Ask tối đa 20 lần. Nếu gọi quá 20 lần, chương trình nhận kết quả Wrong Answer [6].

  Nếu lời gọi Ask bị đánh giá là sai, chương trình kết thúc ngay lúc đó.

Quy trình chấm

Việc chấm được thực hiện theo quy trình sau. Nếu bị đánh giá là sai, chương trình kết thúc ngay lúc đó.

1. Để cung cấp thông tin đường bộ, InitAnya và InitBoris được gọi mỗi hàm một lần theo thứ tự này.

2. Với $i=1,\ldots,Q$, lần lượt thực hiện các thao tác sau.

   1. Gọi Anya đúng một lần. Thao tác này tương ứng với việc Anya quyết định dãy bit lưu trên máy chủ trung gian sau khi thông tin tuyết rơi được cập nhật vào đầu ngày.
   2. Gọi Boris $D_i$ lần. $D_i$ là số câu hỏi của người dân trong ngày $i$. Tham số trong lần gọi thứ $j$ ($1\le j\le D_i$) là $R_{ij}$ ($1\le R_{ij}\le N-1$). Nếu trong lần gọi thứ $j$, giá trị trả về của Boris không bằng số con đường có tuyết rơi ít nhất phải đi qua để di chuyển từ thành phố $0$ đến thành phố $R_{ij}$, chương trình bị đánh giá là sai.

3. Nếu không lần nào bị đánh giá là sai, chương trình được đánh giá là đúng.

Chú ý quan trọng

• Thời gian chạy và bộ nhớ sử dụng được đo cho các bước (1), (2) trong “Quy trình chấm”. Nếu chương trình đúng, ở bước (2), Anya được gọi tổng cộng $Q$ lần và Boris được gọi tổng cộng $D_1+\cdots+D_Q$ lần.
• Anya và Boris không thể biết các giá trị $D_1,\ldots,D_Q$.
• Hàm Boris không được cung cấp thông tin cho biết thời điểm hàm Anya cập nhật dữ liệu lưu trên máy chủ trung gian.
• Bạn được phép cài đặt các hàm khác để dùng nội bộ hoặc khai báo biến toàn cục. Tuy nhiên, hai chương trình nộp sẽ được liên kết cùng chương trình chấm thành một tệp thực thi. Vì vậy, tất cả biến toàn cục và các hàm nội bộ trong mỗi tệp, ngoại trừ InitAnya, Anya, InitBoris, Boris, phải được khai báo static để tránh xung đột với các tệp khác. Khi chấm, chương trình này được chạy thành hai tiến trình ở phía Anya và phía Boris, nên hai phía không thể dùng chung biến toàn cục trong chương trình.
• Bài nộp của bạn không được trao đổi bằng bất kỳ cách nào với đầu vào chuẩn, đầu ra chuẩn hay các tệp khác.

Cách biên dịch và chạy

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

Chương trình chấm mẫu gồm một tệp, grader.c hoặc grader.cpp. Nếu chương trình của bạn là Anya.c và Boris.c, hoặc Anya.cpp và Boris.cpp, hãy chạy các lệnh sau để kiểm thử.

• Với C:

  gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• Với C++:

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

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

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

Tổng quan về chương trình chấm mẫu

Chương trình chấm mẫu gọi các hàm theo “Quy trình chấm”.

Lưu ý điểm sau khác với hành vi của chương trình chấm thật.

• Chương trình chấm mẫu không kiểm tra Wrong Answer [7] mà thay vào đó xuất giá trị trả về của hàm Boris cho mỗi câu hỏi.

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

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

• Dòng đầu chứa số nguyên $N$, cho biết có $N$ thành phố.
• Dòng thứ $i+1$ ($0\le i\le N-2$) trong $N-1$ dòng tiếp theo chứa hai số nguyên $A_i,B_i$ cách nhau bởi dấu cách. Đường $i$ nối hai chiều giữa thành phố $A_i$ và thành phố $B_i$.
• Dòng tiếp theo chứa số nguyên $Q$, cho biết giải đấu diễn ra trong $Q$ ngày.
• Dòng thứ $i$ ($1\le i\le Q$) trong $Q$ dòng tiếp theo chứa một chuỗi $S_i$ dài $N-1$ và $D_i+1$ số nguyên, cách nhau bởi dấu cách. $S_i$ biểu diễn thông tin tuyết rơi của ngày $i$. Ký tự thứ $j+1$ từ trái sang ($0\le j\le N-2$) là 1 nếu đường $j$ có tuyết rơi, hoặc 0 nếu đường $j$ không có tuyết rơi. Số đầu tiên trong $D_i+1$ số nguyên là $D_i$. $D_i$ số tiếp theo là $R_{i1},\ldots,R_{iD_i}$. Điều này nghĩa là câu hỏi thứ $j$ ($1\le j\le D_i$) trong ngày $i$ hỏi số con đường có tuyết rơi ít nhất phải đi qua để di chuyển từ thành phố $0$ đến thành phố $R_{ij}$.

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

Chương trình chấm mẫu xuất các thông tin sau ra đầu ra chuẩn (dấu ngoặc kép không thực sự được xuất).

• Nếu chương trình bị đánh giá là sai trong khi chạy, loại lỗi được xuất dưới dạng như Wrong Answer [1] và chương trình kết thúc.
• Nếu tất cả $D_i$ lần gọi Boris sau lần gọi Anya thứ $i$ ($1\le i\le Q$) đều không bị đánh giá là sai, tại thời điểm đó chương trình xuất một dòng gồm $D_i$ số nguyên cách nhau bởi dấu cách. Số thứ $j$ ($1\le j\le D_i$) là giá trị trả về của Boris với tham số $R_{ij}$.

Nếu chương trình thỏa mãn nhiều điều kiện sai, chỉ một loại lỗi trong số đó được hiển thị.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

• $2\le N\le500$.
• $1\le Q\le500$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le N-2$).
• $1\le D_j$ ($1\le j\le Q$).
• $D_1+\cdots+D_Q\le500$.
• Có thể đi lại giữa hai thành phố khác nhau bất kỳ qua một số con đường.

Nhiệm vụ con

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

• $N\le20$.

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

• $N\le100$.

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

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

• $A_i=i$ ($0\le i\le N-2$).
• $B_i=i+1$ ($0\le i\le N-2$).

Nhiệm vụ con 4 [45 điểm]

Không có giới hạn bổ sung.

Ví dụ giao tiếp

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

Dữ liệu vào 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Ví dụ lời gọi hàm

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

Các tham số truyền cho InitAnya(...), InitBoris(...), lần gọi Anya(...) thứ nhất và thứ hai lần lượt như sau.