A library wants to split
Determine whether such a split is possible.
The twist: placing one student fixes the expected halls of many other students through chains of restrictions.
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of students and restriction pairs.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, meaning students KaTeX can only parse string typed expression and KaTeX can only parse string typed expression must be placed in different halls.
Print KaTeX can only parse string typed expression if the split is possible, otherwise print KaTeX can only parse string typed expression.
Input
4 3
1 2
2 3
3 4YESOne possible split is hall A: KaTeX can only parse string typed expression and hall B: KaTeX can only parse string typed expression.
Example 2:
Input
3 3
1 2
2 3
3 1NOThree students all pairwise conflict, so two halls are not enough.