Maximizing Consistent Message Order

In an online academic community, there are N users with nicknames n₁, n₂, ..., n_N and M messages posted in a thread. Each message i is described by a triple of strings (s_i,1, s_i,2, s_i,3) where:

• s_i,1 is the sender's nickname,
• s_i,2 is a nickname mentioned in the message, and
• s_i,3 describes the type of the message.

All string comparisons are case‐sensitive (for example, 1oushang, Loushang and LOUSHANG are all different strings).

Messages are classified into three types:

• If si,3 = "louxia" and si,2 exactly equals one of the given nicknames (possibly equal to si,1), the message is a downstairs message; the mentioned user is si,2.
• If si,3 = "loushang" and si,2 exactly equals one of the given nicknames, it is an upstairs message; the mentioned user is si,2.
• Otherwise, it is an academic message.

A reordering scheme is a permutation a₁, a₂, ..., a_M of the message indices which arranges the messages in a new order. In this order, the i^th message is (s_ai,1, s_ai,2, s_ai,3).

For each message at position i (1 ≤ i ≤ M) in the reordering:

• If the message is downstairs, it is considered consistent if and only if i ≠ 1 and the sender of the previous message equals the mentioned nickname; that is, sai-1,1 = sai,2.
• If the message is upstairs, it is consistent if and only if i ≠ M and the sender of the next message equals the mentioned nickname; that is, sai+1,1 = sai,2.
• Academic messages are never consistent.

The goal is to reorder the messages so that the number of consistent messages is maximized, and output both the maximum number and one such reordering.

Note: In the given data, every user who posted at least one message has posted at least one academic message.

inputFormat

The input begins with two integers N and M (1 ≤ N, M ≤ ...), where N is the number of users and M is the number of messages.

The second line contains N nonempty strings representing the nicknames (n₁, n₂, ..., n_N).

Each of the next M lines contains three nonempty strings si,1 si,2 si,3 separated by spaces, describing the i^th message.

outputFormat

Output two lines:

1. The first line contains the maximum number of consistent messages.
2. The second line contains M integers—a permutation of 1, 2, ..., M—representing one reordering achieving that maximum.

If there are multiple answers, output any one of them.

sample

3 4
A B C
A A loushang
B A louxia
A B louxia
C C louxia

3
1 3 2 4

</p>