아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

원수의 원수

면접 대비

시간 제한1초메모리 제한512 MB

요약
사람들 사이의 친구와 적 관계가 주어질 때 적의 적은 친구라는 규칙으로 관계를 추론하고, 각 질의에 Friend, Enemy, Unknown, Error 중 하나를 답한다.
난이도

보통10점 중 6점

유형
유니온 파인드, 그래프, DFS, 구현
정답자
아직 제출이 없습니다

문제

"원수의 원수는 친구"라는 속담이 있다. 이 속담을 이용하면 어떤 두 사람의 관계든 알 수 있다. 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≤N≤100,000)N \, (2 \leq N \leq 100,000), 관계의 수 M (0≤M≤100,000)M \, (0 \leq M \leq 100,000), 대답해야 할 관계의 수 K (1≤K≤100,000)K \, (1 \leq K \leq 100,000)가 주어진다.

이어서 MM개의 줄에 걸쳐 t∈{0,1}t \in \{0, 1\}, aa, bb (1≤a,b≤N,a≠b)(1 \leq a, b \leq N, a \neq b)가 주어진다.

t=0t = 0이면 aa와 bb가 친구 관계임을 의미한다.

t=1t = 1이면 aa와 bb가 원수 관계임을 의미한다.

그다음 KK개의 줄에 걸쳐 쿼리 aa, bb (1≤a,b≤N,a≠b)(1 \leq a, b \leq N, a \neq b)가 주어진다.

출력

각 쿼리마다 aa와 bb의 관계를 한 줄에 하나씩 출력한다.

aa와 bb가 전혀 관련이 없으면 'Unknown'을 출력한다.

aa와 bb가 친구 관계이면 'Friend'를 출력한다.

aa와 bb가 원수 관계이면 'Enemy'를 출력한다.

aa와 bb가 친구 관계이면서 원수 관계이면 'Error'를 출력한다.

힌트

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

예제2

  1. 예제 1

    입력
    5 4 4
    1 1 2
    1 2 3
    0 3 4
    0 4 5
    1 3
    2 4
    3 5
    1 5
    
    예상 출력
    Friend
    Enemy
    Friend
    Friend
    
  2. 예제 2

    입력
    5 4 3
    1 1 2
    0 2 3
    0 1 3
    0 1 5
    1 4
    1 2
    1 5
    
    예상 출력
    Unknown
    Error
    Error