Enemy of My Enemy
InterviewTime limit1sMemory limit512 MB
Given friend and enemy relations between people, derive implied relations using the enemy-of-my-enemy rule, then answer queries with Friend, Enemy, Unknown, or Error.
- Level
Medium6 of 10
- Topics
- Union-find, Graph, DFS, Implementation
- Solved
- No attempts yet
Problem
There is a saying, "the enemy of my enemy is my friend." With this saying, we can determine the relationship of any two people. Even if A and C have no direct relationship, if A and B have a relationship and B and C have a relationship, then A and C also have an indirect relationship. This is summarized as follows.
- If A and B are enemies and B and C are enemies, then A and C are friends.
- If A and B are enemies and B and C are friends, then A and C are enemies.
- If A and B are friends and B and C are friends, then A and C are friends.
Based on this, given the relationships between people, let us determine the relationship between specific people.
Input
The first line contains the number of people , the number of relationships , and the number of relationships to answer .
Then lines follow, each containing , , .
If , it means and are friends.
If , it means and are enemies.
Then lines follow, each containing a query , .
Output
For each query, output the relationship between and on its own line.
If and are not related at all, output 'Unknown'.
If and are friends, output 'Friend'.
If and are enemies, output 'Enemy'.
If and are both friends and enemies, output 'Error'.
Hint
In the second example, 1 and 2 are directly enemies, but 1 and 3 are friends and 2 and 3 are friends, so they are indirectly friends. Therefore, 1 and 2 are both enemies and friends, resulting in Error.