Who is taller?

Interview

Time limit1sMemory limit128 MB

Summary
Given comparisons stating x is taller than y, decide whether p is taller than q, q is taller than p, or neither is known.
Level

Medium4 of 10

Topics
Graph, DFS, BFS
Solved
No attempts yet

Problem

You have a few minutes before your class starts, so you decide to compare the heights of your classmates. You don't have an accurate measuring device, so you only compare two people at a time: you stand them back-to-back and see which one is taller. Conveniently, no two classmates have exactly the same height, and you never make a mistake in a comparison.

After finishing all of your comparisons, you want to determine which of two particular classmates is taller.

Input

The first line contains two integers NN and MM separated by a single space. NN, the number of people in the class, satisfies 1≤N≤1,000,0001 \le N \le 1{,}000{,}000. MM, the number of comparisons already made, satisfies 1≤M≤10,000,0001 \le M \le 10{,}000{,}000.

Each of the next MM lines contains two distinct integers xx and yy (1≤x,y≤N1 \le x, y \le N) separated by a space, meaning that person xx was found to be taller than person yy.

The last line contains two distinct integers pp and qq (1≤p,q≤N1 \le p, q \le N) separated by a single space. Your goal is to determine, if possible, whether person pp is taller than person qq.

It is possible that neither pp nor qq appears in any comparison, and each comparison between a given pair of people is recorded exactly once.

Output

Print a single line containing one of the following three strings:

  • yes — if pp is taller than qq,
  • no — if qq is taller than pp,
  • unknown — if there is not enough information to determine the relative heights of pp and qq.

Examples3

  1. Example 1

    Input
    10 3
    8 4
    3 8
    4 2
    3 2
    
    Expected output
    yes
    
  2. Example 2

    Input
    10 3
    8 4
    3 8
    4 2
    2 3
    
    Expected output
    no
    
  3. Example 3

    Input
    5 2
    1 2
    3 4
    2 4
    
    Expected output
    unknown