Magical Creatures Bipartition

In a magical realm, each creature forms friendships that might connect them in complex ways. Your task is to determine whether it is possible to partition all the magical creatures into two groups such that every friendship connects a creature from one group to a creature from the other. In other words, there should be no pair of friends within the same group.

Formally, given (n) creatures and (m) bidirectional friendship connections, determine if the underlying graph is bipartite. If it is, output YES followed by the list of creature labels in Group 1 and Group 2 (each group sorted in increasing order). Otherwise, output NO.

inputFormat

The input is read from standard input (stdin). The first line contains two integers, (n) and (m), representing the number of creatures and the number of friendship connections respectively. Each of the next (m) lines contains two integers (a) and (b) ((1 \leq a, b \leq n)), indicating that creature (a) and creature (b) are friends.

outputFormat

Print the result to standard output (stdout). If the creatures can be partitioned into two groups following the rules, print YES on the first line, followed by a line containing the sorted list of creature labels in Group 1, and then a line containing the sorted list of creature labels in Group 2 (if a group is empty, print an empty line). If the partition is not possible, print only NO.## sample

5 4
1 2
2 3
3 4
4 5

YES
1 3 5
2 4