시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB32213310542.339%

문제

원수의 원수는 친구라는 속담이 있다! 이 속담과 함께라면 어떤 두 사람이든 그 쌍의 관계를 알 수 있다. A와 C라는 사람이 직접적으로 관계가 없더라도, A와 B가 관계가 있고 B와 C가 관계가 있다면 A와 C라는 사람도 간접적으로 관계가 있다. 이를 정리하면 아래와 같다.

  1. A와 B가 원수 관계이고 B와 C가 원수 관계이면 A와 C는 친구 관계이다.
  2. A와 B가 원수 관계이고 B와 C가 친구 관계이면 A와 C는 원수 관계이다.
  3. A와 B가 친구 관계이고 B와 C가 친구 관계이면 A와 C는 친구 관계이다.

이를 바탕으로 사람들 간의 관계가 주어질 때, 특정 사람 간의 관계가 무엇인지를 확인해보자!

입력

사람의 수 $N \, (2 \leq N \leq 100,000)$과 관계의 수 $M \, (0\leq M \leq 100,000)$, 그리고 대답해야 할 관계의 수 $K \, (1\leq K \leq 100,000)$가 입력으로 들어온다.

그 후 $M$개의 줄에 걸쳐 $t \in \{0, 1\}$, $a$, $b$ $(1\leq a, b \leq N, a \neq b)$가 입력으로 들어오게 된다.

$t$ = 0일 경우 $a$, $b$가 친구 관계임을 의미한다.

$t$ = 1일 경우 $a$, $b$가 원수 관계임을 의미한다.

그 후 $K$개의 줄에 걸쳐 쿼리 $a$, $b$ $(1\leq a, b \leq N, a \neq b)$가 입력으로 들어오게 된다.

출력

각 쿼리에 대해 $a$와 $b$의 관계를 각 줄마다 출력하면 된다.

$a$와 $b$가 전혀 관련이 없을 경우 'Unknown'을 출력한다.

$a$와 $b$가 친구 관계인 경우 'Friend'를 출력한다.

$a$와 $b$가 원수 관계인 경우 'Enemy'를 출력한다.

$a$와 $b$가 친구 관계이자 원수 관계인 경우 'Error'를 출력한다.

예제 입력 1

5 4 4
1 1 2
1 2 3
0 3 4
0 4 5
1 3
2 4
3 5
1 5

예제 출력 1

Friend
Enemy
Friend
Friend

예제 입력 2

5 4 3
1 1 2
0 2 3
0 1 3
0 1 5
1 4
1 2
1 5

예제 출력 2

Unknown
Error
Error

힌트

두번째 예제의 경우, 1과 2는 직접적으로 원수 관계이지만, 1과 3 그리고 2와 3이 친구 관계이므로 간접적으로 친구 관계이다. 따라서 1과 2는 원수 관계이면서도 친구 관계가 되어 Error가 된다.

출처

University > POSTECH > 2021 POSTECH Programming Contest F번