← 返回题目列表

Codeforces · 754/C

C. 弗拉迪克和聊天

中文机器翻译题面 查看原题

最近,Vladik 发现了一种新的娱乐——社交网络编码机器人。他想在他的机器人中使用机器学习,所以现在他想为它们准备一些学习数据。

首先,他需要下载t个聊天记录。弗拉迪克(Vladik)编写了一个应该下载聊天记录的脚本,但是出了问题。特别是,有些消息没有发送者的信息。众所周知,如果一个人连续发送多条消息,它们都会合并为一条消息。这意味着同一发件人不能连续存在两条或更多条消息。此外,发件人绝不会在消息中提及自己。

Vladik 希望恢复所有消息的发件人,以便每两条相邻消息都有不同的发件人,并且没有发件人会在消息中提及自己。

他不知道如何执行此操作,并向您寻求帮助。帮助 Vladik 恢复每个聊天中的发件人!

输入

第一行包含单个整数 t (1 ≤ t ≤ 10) — 聊天数量。 t 聊天如下。每个聊天都按以下格式给出。

每个聊天描述的第一行包含单个整数 n (1 ≤ n ≤ 100) — 聊天中的用户数量。

下一行包含 n 个以空格分隔的不同用户名。每个用户名由小写和大写英文字母和数字组成。用户名不能以数字开头。两个用户名是不同的,即使它们仅字母大小写不同。用户名长度为正数且不超过10个字符。

下一行包含单个整数 m (1 ≤ m ≤ 100) — 聊天中的消息数。接下来的 m 行包含以下格式的消息,每行一条:

- <用户名>:<文本> — 已知发件人的消息格式。用户名应出现在聊天的用户名列表中。
- <?>:<text> — 发件人未知的消息格式。

消息正文可以由大小写英文字母、数字、字符“.”组成(点), ',' (逗号), '!' (感叹号), '?' (问号)和“ ”(空格)。文本不包含尾随空格。文本长度为正数且不超过 100 个字符。

如果用户的用户名作为单词出现在文本中,我们就说文本提及了该用户。换句话说,用户名出现的位置,其出现前后的两个字符要么不存在,要么不是英文字母或数字。例如,文本“Vasya、masha13 和 Kate!”可以提及用户“Vasya”、“masha13”、“and”和“Kate”,但不能提及“masha”。

保证在每个聊天中没有已知发件人在其消息中提及自己,并且不存在具有同一已知发件人的两条相邻消息。

输出

按以下格式打印有关 t 聊天的信息:

如果无法恢复发件人,请为此聊天打印单行“Impossible”。否则按以下格式打印 m 条消息:

<用户名>:<文本>

如果有多个答案,请打印其中任何一个。

示例

输入 #1

1
2
Vladik netman
2
?: Hello, Vladik!
?: Hi

输出 #1

netman: Hello, Vladik!
Vladik: Hi

输入 #2

1
2
netman vladik
3
netman:how are you?
?:wrong message
vladik:im fine

输出 #2

Impossible

输入 #3

2
3
netman vladik Fedosik
2
?: users are netman, vladik, Fedosik
vladik: something wrong with this chat
4
netman tigerrrrr banany2001 klinchuh
4
?: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready?
klinchuh: yes, coach!
?: yes, netman
banany2001: yes of course.

输出 #3

Impossible
netman: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready?
klinchuh: yes, coach!
tigerrrrr: yes, netman
banany2001: yes of course.