Tên của nàng
Đề bài
Mô tả
Trong Hoàng tộc, tên gọi là điều vô cùng quan trọng! Là Sử gia Hoàng gia, bạn được giao nhiệm vụ phân tích các quy luật trong tên của các Công nương trong vương quốc.
Đã có Công nương, để tiện ta đánh số từ đến . Tên của mỗi Công nương là một chữ cái in hoa ghép với tên của mẹ cô. Ngoại lệ duy nhất là Công nương số , người sáng lập Hoàng tộc, có tên chỉ gồm một chữ cái in hoa.
Ví dụ, ENERYS có thể là mẹ của AENERYS (vì tên AENERYS gồm chữ cái in hoa A ghép với ENERYS, tên của mẹ cô). Tương tự, AENERYS có thể là mẹ của DAENERYS và YAENERYS.
Cho mô tả của tất cả các Công nương. Nhiệm vụ của bạn là xác định, với một số xâu đáng chú ý, số Công nương có là tiền tố của tên mình.
Ví dụ, xét ví dụ thứ nhất dưới đây: dòng dõi đi thẳng từ người sáng lập S tới AENERYS (qua YS, RYS, ERYS, NERYS và ENERYS), mỗi Công nương có đúng một con gái. Sau đó AENERYS có hai con gái là DAENERYS và YAENERYS, và YAENERYS có một con gái là RYAENERYS.
tree parent 1 2 3 4 5 6 7 7 9 label 1 S label 2 YS label 3 RYS label 4 ERYS label 5 NERYS label 6 ENERYS label 7 AENERYS label 8 DAENERYS label 9 YAENERYS label 10 RYAENERYS
Trong Hoàng tộc này, RY là tiền tố của tên hai Công nương: RYS và RYAENERYS. E là tiền tố của tên ERYS và ENERYS. N chỉ là tiền tố của tên NERYS, còn S chỉ là tiền tố của tên người sáng lập S. AY không là tiền tố của tên Công nương nào.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , trong đó là tổng số Công nương và là số xâu truy vấn.
Tiếp theo là dòng mô tả các Công nương. Dòng thứ mô tả Công nương số , gồm một chữ cái in hoa (từ A đến Z) và một số nguyên , trong đó là chữ cái đầu tiên trong tên Công nương , còn là số hiệu của mẹ cô (hoặc với Công nương đầu tiên). Tên của tất cả các Công nương đôi một khác nhau.
dòng còn lại, mỗi dòng chứa một xâu truy vấn khác rỗng chỉ gồm các chữ cái in hoa.
Dữ liệu ra
In ra dòng, dòng thứ chứa số Công nương có xâu truy vấn thứ là tiền tố của tên mình.
Ràng buộc
- .
- .
- và với .
- Tổng độ dài các xâu truy vấn không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 5 S 0 Y 1 R 2 E 3 N 4 E 5 A 6 D 7 Y 7 R 9 RY E N S AY |
2 2 1 1 0 |
Hoàng tộc trong hình trên. RY là tiền tố của RYS và RYAENERYS; E là tiền tố của ERYS và ENERYS; N chỉ của NERYS; S chỉ của S; AY không của ai. |
| 8 3 C 0 A 1 E 1 A 3 D 1 B 3 C 4 B 6 EA CB A |
0 0 2 |
Tên các Công nương lần lượt là C, AC, EC, AEC, DC, BEC, CAEC, BBEC. Không tên nào bắt đầu bằng EA hay CB; A là tiền tố của AC và AEC. |
Bình luận