This page is still under construction.

Parts of this page are still being built. What you see may change.

Enemy of My Enemy

Interview

Time limit1sMemory limit512 MB

Summary
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.

  1. If A and B are enemies and B and C are enemies, then A and C are friends.
  2. If A and B are enemies and B and C are friends, then A and C are enemies.
  3. 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 N (2≤N≤100,000)N \, (2 \leq N \leq 100,000), the number of relationships M (0≤M≤100,000)M \, (0 \leq M \leq 100,000), and the number of relationships to answer K (1≤K≤100,000)K \, (1 \leq K \leq 100,000).

Then MM lines follow, each containing t∈{0,1}t \in \{0, 1\}, aa, bb (1≤a,b≤N,a≠b)(1 \leq a, b \leq N, a \neq b).

If t=0t = 0, it means aa and bb are friends.

If t=1t = 1, it means aa and bb are enemies.

Then KK lines follow, each containing a query aa, bb (1≤a,b≤N,a≠b)(1 \leq a, b \leq N, a \neq b).

Output

For each query, output the relationship between aa and bb on its own line.

If aa and bb are not related at all, output 'Unknown'.

If aa and bb are friends, output 'Friend'.

If aa and bb are enemies, output 'Enemy'.

If aa and bb 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.

Examples2

  1. Example 1

    Input
    5 4 4
    1 1 2
    1 2 3
    0 3 4
    0 4 5
    1 3
    2 4
    3 5
    1 5
    
    Expected output
    Friend
    Enemy
    Friend
    Friend
    
  2. Example 2

    Input
    5 4 3
    1 1 2
    0 2 3
    0 1 3
    0 1 5
    1 4
    1 2
    1 5
    
    Expected output
    Unknown
    Error
    Error