printРабочее место участника


2018. Join the Conversation

Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Abstract Communication Mastership (ACM) is a software company that develops a unique social network called tWinter.
Each tWinter user has a handle that starts with a commercial at (‘@’) character. Users of tWinter social network publish short messages to the network.
If a user’s message contains another user’s handle (preceded by a space or at the beginning of the message, and followed by a space or at the end of the message) then it is called a mention.
A sequence of messages is called a conversation if each message in the sequence (except the first one) contains a mention of the author of the previous message in the sequence.
You are hired to find the longest conversation in the given chronological log of messages.
The first line of the input file contains an integer `n` (`1\ ≤\ n\ ≤\ 50\ 000`) — the number of messages in the chronological log.
Each of the next `n` lines contains a message preceded by its author’s handle, a colon (‘:’) character, and a space.
Each message is at most 139 characters long. Each handle is at most 20 characters long and does not contain colons or spaces.
The input file contains only characters with ASCII codes between 32 and 126, inclusive, and line breaks
On the first line of the output file write the length of the longest conversation in the given log. On the second line write 1-based indices of the messages in that conversation in ascending order.
If there are multiple longest conversations, write any one of them.

Sample Input

@Petr: Leaving for #NEERC tomorrow!
@Roman: This #NEERC is going to be awesome!
@Stone in forest: Nothing happened today.
@NEERCNews: @Petr Don’t forget an umbrella :)
@Lydia: @NEERCNews cares about @Petr - so cute ^ ^
@Lydia: @Lydia @NEERCNews @Petr it won’t be raining though!

Sample Output

1 4 5
Source: ACM ICPC NEERC, 2013