Truth-tellers and Liars Partition

You are given a group of n persons and m pairwise relationships. Each relationship is between two distinct persons. The task is to determine whether it is possible to partition the set of persons into two groups - one representing truth-tellers and the other representing liars - such that for every given pair, the two persons belong to different groups.

This problem can be modeled as a graph \(G = (V, E)\) where \(V = \{1, 2, \ldots, n\}\) represents the persons and each edge \((u, v) \in E\) represents a relationship between person \(u\) and person \(v\). A valid partition exists if and only if the graph is bipartite.

If a valid partition exists, output "YES" in the first line, followed by two lines that describe the two partitions. The second line should contain the number of persons in the first group followed by their labels, and the third line should contain the number of persons in the second group followed by their labels. If no valid partition exists, output "NO".

inputFormat

The input is read from stdin and has the following format:

n m
u1 v1
u2 v2
... 
um vm

Where the first line contains two integers \(n\) and \(m\), representing the number of persons and the number of relationships respectively. Each of the next \(m\) lines contains two integers \(u\) and \(v\), indicating that person \(u\) and person \(v\) have a relationship. Persons are numbered from 1 to \(n\).

outputFormat

The output should be written to stdout as follows:

• If a valid partition exists, print three lines:
• The first line contains the string "YES".
• The second line starts with the number of persons in the first group followed by their labels separated by spaces.
• The third line starts with the number of persons in the second group followed by their labels separated by spaces.
• If no valid partition exists, print a single line with the string "NO".

## sample

4 4
1 2
2 3
3 4
4 1

YES
2 1 3
2 2 4

</p>