누가 더 큰가?

면접 대비

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

요약
x가 y보다 크다는 비교 결과가 주어질 때, p가 q보다 큰지, q가 p보다 큰지, 아니면 알 수 없는지 판정한다.
난이도

보통10점 중 4점

유형
그래프, DFS, BFS
정답자
아직 제출이 없습니다

문제

수업이 시작되기 전 잠깐의 시간 동안, 여러분은 반 친구들의 키를 비교해 보기로 했습니다. 정확한 측정 도구가 없기 때문에, 두 사람을 등지고 서게 한 뒤 둘 중 누가 더 큰지 눈으로 비교하는 방식만 사용합니다. 다행히 같은 키를 가진 친구는 아무도 없으며, 여러분의 비교는 항상 정확합니다(즉, 비교 결과에 오류가 없습니다).

모든 비교를 마친 뒤, 특정한 두 친구 중 누가 더 큰지 판단하려고 합니다.

입력

첫째 줄에 두 정수 NN과 MM이 공백 하나로 구분되어 주어집니다. NN은 반의 인원 수로 1≤N≤1,000,0001 \le N \le 1{,}000{,}000을 만족하는 정수이고, MM은 이미 수행한 비교의 횟수로 1≤M≤10,000,0001 \le M \le 10{,}000{,}000을 만족하는 정수입니다.

이어지는 MM개의 줄에는 각각 서로 다른 두 정수 xx와 yy(1≤x,y≤N1 \le x, y \le N)가 공백으로 구분되어 주어지며, 이는 xx번 사람이 yy번 사람보다 더 크다고 판정되었음을 뜻합니다.

마지막 줄에는 서로 다른 두 정수 pp와 qq(1≤p,q≤N1 \le p, q \le N)가 공백 하나로 구분되어 주어집니다. 목표는 가능하다면 pp번 사람이 qq번 사람보다 더 큰지 판단하는 것입니다.

pp나 qq가 비교 기록에 전혀 등장하지 않을 수도 있으며, 임의의 두 사람 사이의 비교는 정확히 한 번만 기록됩니다.

출력

한 줄에 다음 세 문자열 중 하나를 출력합니다.

  • yes — pp가 qq보다 더 큰 경우
  • no — qq가 pp보다 더 큰 경우
  • unknown — pp와 qq의 상대적인 키를 판단하기에 정보가 부족한 경우

예제3

  1. 예제 1

    입력
    10 3
    8 4
    3 8
    4 2
    3 2
    
    예상 출력
    yes
    
  2. 예제 2

    입력
    10 3
    8 4
    3 8
    4 2
    2 3
    
    예상 출력
    no
    
  3. 예제 3

    입력
    5 2
    1 2
    3 4
    2 4
    
    예상 출력
    unknown