#O. 家谱

    Type: Default 1000ms 256MiB

家谱

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

现代的人对于本家族血统越来越感兴趣。

Description

给出充足的父子关系,请你编写程序找到某个人的最早的祖先。

Format

Input

输入由多行组成,首先是一系列有关父子关系的描述,其中每一组父子关系中父亲只有一行,儿子可能有若干行,用 #name 的形式描写一组父子关系中的父亲的名字,用 +name 的形式描写一组父子关系中的儿子的名字;接下来用 ?name 的形式表示要求该人的最早的祖先;最后用单独的一个 $ 表示文件结束。

Output

按照输入文件的要求顺序,求出每一个要找祖先的人的祖先,格式为:本人的名字 ++ 一个空格 ++ 祖先的名字 ++ 回车。

Samples

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$
Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

Limitation

1s, 1024KiB for each test case.

规定每个人的名字都有且只有 6 个字符,而且首字母大写,且没有任意两个人的名字相同。最多可能有 10^3 组父子关系,总人数最多可能达到 5×10^4人,家谱中的记载不超过 30 代。

这个题数据还有点水,以可能会重判。

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45