GJX与死锁
题号:NC54280
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

死锁,是指多个进程在运行过程中因争夺资源而造成的一种僵局,当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。

A set of processes is deadlocked when each process in the set is blocked awaiting an event that can only be triggered by another blocked process in the set.

一组进程是死锁的,如果其中每个进程因等待事件而阻塞,且所等待的事件只能被这组进程中的另一阻塞进程激发。


现在,GJX拥有n个进程。为了简化问题,每个进程占用1个资源,请求1个资源。任一时刻只允许一个进程使用资源,进程在请求其余资源时,不主动释放已经占用的资源,进程已经占用的资源,不会被强制剥夺。现在请你编写程序,确认是否会发生死锁。

输入描述:

第一行,一个数n,表示进程数量。

接下来n行,每一行两个数,代表每个进程所占用的资源及请求的资源。

输出描述:

一行,若会发生死锁,则输出YES,反之,输出NO。
示例1

输入

复制
4
1 2
2 3
3 4
4 1

输出

复制
YES
示例2

输入

复制
4
1 2
3 2
5 4
6 4

输出

复制
NO

备注:

1<=n<=200000,资源编号小于500000