DAG Trio (Hard)

This issue is the same configuration issue as D: DAG Trio (Easy), with only the constraints being different.

input

$N \ M$ $a_1 \ b_1$ $a_2 \ b_2$ $\ vdots$ $a_M \ b_M$

output

Print "YES" or "NO" on the $1$ line.

Example

Input

3 3 1 2 2 3 3 1

Output

YES

inputFormat

input

$N \ M$ $a_1 \ b_1$ $a_2 \ b_2$ $\ vdots$ $a_M \ b_M$

outputFormat

output

Print "YES" or "NO" on the $1$ line.

Example

Input

3 3 1 2 2 3 3 1

Output

YES

样例

3 3
1 2
2 3
3 1

YES