Nhà thực vật học Somhed thường xuyên đưa các nhóm học sinh đến một trong những vườn nhiệt đới lớn nhất Thái Lan. Khu vườn có \(N\) đài phun nước, được đánh số từ \(0\) đến \(N-1\), và \(M\) đường mòn. Mỗi đường mòn nối hai đài phun nước khác nhau và có thể đi theo cả hai chiều. Không có hai đường mòn nào nối cùng một cặp đài phun nước. Từ mỗi đài phun nước đều có ít nhất một đường mòn đi ra. Dọc các đường mòn là những bộ sưu tập thực vật đẹp mà Somhed muốn ngắm nhìn. Mỗi nhóm có thể bắt đầu chuyến đi tại bất kỳ đài phun nước nào.

Somhed yêu thích những loài cây nhiệt đới đẹp. Vì vậy, tại mỗi đài phun nước, ông và các học sinh sẽ chọn đường mòn đẹp nhất đi ra từ đó, trừ khi đó chính là đường mòn vừa đi qua và vẫn còn đường khác để chọn. Trong trường hợp ấy, họ chọn đường mòn đẹp thứ hai. Nếu không có lựa chọn nào khác, họ buộc phải quay lại theo đường mòn vừa đi qua. Với con mắt của một nhà thực vật học chuyên nghiệp, Somhed không bao giờ đánh giá hai đường mòn đẹp như nhau.

Các học sinh không mấy quan tâm đến cây cối, nhưng rất muốn ăn trưa tại một nhà hàng cao cấp nằm cạnh đài phun nước số \(P\). Somhed biết rằng mỗi nhóm sẽ đói sau khi đi qua đúng \(K\) đường mòn; giá trị \(K\) có thể khác nhau giữa các nhóm. Ông muốn biết có bao nhiêu lộ trình khác nhau để chọn cho mỗi nhóm, sao cho nhóm có thể xuất phát tại bất kỳ đài phun nước nào, luôn chọn đường theo quy tắc trên và kết thúc tại đài phun nước \(P\) sau khi đi qua đúng \(K\) đường mòn. Một nhóm có thể đi qua \(P\) trước khi kết thúc lộ trình, nhưng vẫn phải ở \(P\) sau đúng \(K\) lần đi qua đường mòn.

Yêu cầu

Cho thông tin về các đài phun nước và đường mòn, hãy tìm câu trả lời cho \(Q\) nhóm học sinh, tương ứng với \(Q\) giá trị của \(K\).

Cài đặt thủ tục sau, được khai báo trong garden.h:

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]);

• N: số đài phun nước, được đánh số từ \(0\) đến \(N-1\).
• M: số đường mòn, được đánh số từ \(0\) đến \(M-1\). Các đường được cho theo thứ tự độ đẹp giảm dần: với \(0 \le i < M-1\), đường \(i\) đẹp hơn đường \(i+1\).
• P: số hiệu đài phun nước cạnh nhà hàng, \(0 \le P < N\).
• R: mảng hai chiều mô tả các đường mòn. Với \(0 \le i < M\), đường \(i\) nối R[i][0] và R[i][1]. Hai đầu mút khác nhau và không có hai đường cùng nối một cặp đài phun nước.
• Q: số nhóm học sinh.
• G: mảng một chiều chứa các giá trị \(K\). Với \(0 \le i < Q\), nhóm \(i\) sẽ đi qua đúng G[i] đường mòn.

Với mỗi \(i\) từ \(0\) đến \(Q-1\), thủ tục phải tính số lộ trình hợp lệ gồm đúng G[i] lần đi qua đường mòn và kết thúc tại \(P\). Để báo một câu trả lời bằng X, gọi thủ tục do trình chấm cung cấp trong gardenlib.h:

void answer(int x);

Phải gọi answer đúng \(Q\) lần, theo đúng thứ tự các nhóm trong mảng G. Nếu một nhóm không có lộ trình hợp lệ, gọi answer(0). Thủ tục count_routes không trả về giá trị.

Ví dụ

6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2

Correct.

    ![Hình 1: Các đài phun nước và số hiệu đường mòn trong ví dụ 1](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_163be40d.png)

    Các đường mòn được liệt kê theo độ đẹp giảm dần: đường $0$ đẹp nhất, đường $1$ đẹp thứ hai, v.v. Chỉ có hai lộ trình hợp lệ gồm đúng $3$ lần đi qua đường mòn:


    - $1 \to 2 \to 1 \to 0$.
    - $5 \to 4 \to 3 \to 0$.

    Lộ trình thứ nhất bắt đầu tại đài phun nước $1$. Đường đẹp nhất từ đây dẫn đến đài phun nước $2$. Tại $2$, nhóm không có lựa chọn nào khác nên phải quay lại theo cùng đường. Khi trở về $1$, nhóm tránh đường $0$ vừa đi và chọn đường $1$, dẫn đến đài phun nước $P=0$. Vì vậy, thủ tục phải gọi `answer(2)`.

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

Correct.

    ![Hình 2: Các đài phun nước và số hiệu đường mòn trong ví dụ 2](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_d5e5b251.png)

    Với nhóm thứ nhất, chỉ có một lộ trình đến đài phun nước $2$ sau đúng $3$ lần đi qua đường mòn: $1 \to 0 \to 1 \to 2$. Với nhóm thứ hai, có hai lộ trình đến đài phun nước $2$ sau đúng $1$ lần đi qua đường mòn: $3 \to 2$ và $4 \to 2$. Do đó, `count_routes` phải gọi `answer(1)` trước, rồi gọi `answer(2)`.

Ràng buộc

Trong mọi nhóm, \(0 \le P < N\), mỗi đường mòn nối hai đài phun nước phân biệt và mỗi đài phun nước có ít nhất một đường mòn đi ra. Các giới hạn cụ thể của từng nhóm được cho dưới đây.

Phân nhóm

Chi tiết cài đặt

Giới hạn thời gian CPU: 5 giây. Giới hạn bộ nhớ: 256 MB. Không có giới hạn riêng cho bộ nhớ ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là garden/. Thí sinh cài đặt garden.c, garden.cpp hoặc garden.pas. Giao diện của thí sinh là garden.h hoặc garden.pas; giao diện của trình chấm là gardenlib.h hoặc gardenlib.pas. Trình chấm mẫu được cung cấp trong grader.c, grader.cpp hoặc grader.pas.

Dữ liệu vào

Các tệp đầu vào mẫu là grader.in.1, grader.in.2, … Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): ba số nguyên \(N\), \(M\), \(P\).
• Các dòng \(2\) đến \(M+1\): mô tả các đường mòn. Dòng \(i+2\) chứa R[i][0] và R[i][1], cách nhau bởi dấu cách, với \(0 \le i < M\).
• Dòng \(M+2\): số nguyên \(Q\).
• Dòng \(M+3\): các phần tử của mảng \(G\), cách nhau bởi dấu cách.
• Dòng \(M+4\): \(Q\) đáp án mong đợi theo thứ tự các nhóm, cách nhau bởi dấu cách.

Dữ liệu ra

Kết quả mong đợi tương ứng nằm trong grader.expect.1, grader.expect.2, … Mỗi tệp này chứa đúng văn bản Correct..

Nguồn

IOI 2011, ngày thi 1, Pattaya, Thái Lan. Đề Tropical Garden, bản tiếng Anh 1.5: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.