Longest Conversation on tWinter

Abstract Communication Mastership (ACM) develops the unique social network tWinter where each user has a handle starting with the '@' character. Users post short messages and may mention other users. A mention is defined as a handle that appears as a separate token in the message (i.e. it is either at the beginning of the message or preceded by a space, and either at the end of the message or followed by a space).

A sequence of messages forms a conversation if for every message in the sequence (except the first) the message contains a mention of the author of the previous message in the sequence. Each message in the log is given in chronological order. Note that the author of a message is the first token of the message. Your task is to determine the length of the longest conversation that can be extracted from the log. The conversation messages need not be consecutive in the log; they just have to preserve the order.

For example, consider the following log:

4
@alice Hi everyone
@bob Hello @alice how are you
@carol I think @bob is right
@dave I'm not sure @carol

The longest conversation is the entire sequence, which has a length of 4.

inputFormat

The first line contains a single integer N which is the number of messages in the log. Each of the following N lines contains a message. Each message is a non-empty string where the first token is the author’s handle (which always begins with '@') and the rest of the message may contain zero or more mentions. A mention is recognized if a token exactly matches a handle (i.e., starts with '@'). Tokens in a message are separated by spaces.

outputFormat

Output a single integer representing the length of the longest conversation found in the log.

sample

4
@alice Hi everyone
@bob Hello @alice how are you
@carol I think @bob is right
@dave I'm not sure @carol

4