1462: 2-sat问题
Memory Limit:64 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:55
Solved:13
Description
你有$n$个同学,编号$1∼n$,他们的身高两两不同,他们进行了$m$次两两之间的身高比较,你获知了全部结果
请你根据以上所有信息进行判断,学生$p$是否比学生$q$更高。
Input
第一行包含整数 $n$,$m$.
接下来 $m$ 行,每行包含两个不同的整数$x,y$,表示学生$x$比学生$y$高.
最后一行,包含两个不同的整数$p,q$.
输入保证,任何一对同学之间的比较结果,最多只出现一次.
数据范围:$1\leq n\leq 1e6$
$1\leq m\leq 1e7$
$1\leq x,y\leq n$
$1\leq p,q \leq n$
接下来 $m$ 行,每行包含两个不同的整数$x,y$,表示学生$x$比学生$y$高.
最后一行,包含两个不同的整数$p,q$.
输入保证,任何一对同学之间的比较结果,最多只出现一次.
数据范围:$1\leq n\leq 1e6$
$1\leq m\leq 1e7$
$1\leq x,y\leq n$
$1\leq p,q \leq n$
Output
如果学生$p$比学生$q$高,则输出$yes$
如果学生$p$比学生$q$矮,则输出$no$
如果无法判断两人中谁更高,则输出$unknown$
如果学生$p$比学生$q$矮,则输出$no$
如果无法判断两人中谁更高,则输出$unknown$
Sample Input Copy
10 3
8 4
3 8
4 2
3 2
Sample Output Copy
yes