Social Likes: Best Friends and Friend Recommendations

Problem: Social Likes

Consider a simplified social-network model with these properties:

• Friend relationships work in both directions.
• A user can like more than one item.
• Two users' similarity score is the count of items liked by both users.

Your task is to support the following two query forms.

Query 1: BEST user k

For user, output at most k of their strongest friends.

Only direct friends of user may be selected. Order those friends according to these rules:

1. A larger number of shared liked items comes first.
2. When two friends have the same score, the user id that is lexicographically earlier comes first.

When user has fewer than k direct friends, return every direct friend.

Query 2: RECOMMEND user k

Find up to k potential new friends for user.

Apply the following traversal procedure:

1. Visit user's best friends in the order produced by BEST user.
2. For each such best friend bf, visit the users returned by BEST bf, preserving that order.
3. Consider cand as a recommendation only when all of the following hold:
   • cand is different from user;
   • cand is not a direct friend of user;
   • cand has not already been recommended.
4. If cand is already directly connected to user, ignore it and keep looking at later candidates.
5. Finish as soon as k recommendations have been collected or there are no candidates left to inspect.

Input Format

F L Q
Next F lines: userA userB, meaning userA and userB are friends
Next L lines: user item, meaning user liked item
Next Q lines: either BEST user k or RECOMMEND user k

Additional input details:

• User ids and item ids contain no spaces.
• Repeated friendship or like records are possible, and each duplicate should count only once.
• A user mentioned by a query may have neither friends nor liked items.

Output Format

Write one line for every query:

• For a non-empty result, list the user ids with , between adjacent ids.
• For an empty result, write EMPTY.

Constraints

• 0 <= F <= 2 * 10^5
• 0 <= L <= 2 * 10^5
• 1 <= Q <= 2 * 10^5
• The complete set of friendship and like records fits in memory.

Example

Input:

4 9 2
alice bob
alice carol
bob dave
bob erin
alice x
alice y
bob x
bob z
carol y
carol z
dave x
dave z
erin z
BEST alice 2
RECOMMEND alice 2

Output:

bob,carol
dave,erin