Bipartite Graph Partition

You are given an undirected graph with n nodes and m edges. The nodes are numbered from 1 to n. Your task is to determine whether it is possible to partition the nodes into two non-empty subsets such that no two nodes within the same subset are adjacent (i.e. there is no edge connecting any two nodes in the same subset). In other words, you must determine if the graph is bipartite.

If the graph is bipartite, output "YES" on the first line. On the second line, output two integers representing the sizes of the two partitions. The third and fourth lines should list the nodes belonging to the first and the second partition respectively, with nodes separated by spaces. If the graph is not bipartite, simply output "NO".

Note: Input is given via standard input and output must be produced on standard output.

The bipartite condition can be formally stated as follows in LaTeX:

\( \text{A graph } G \text{ is bipartite if } \exists\; V_1, V_2 \text{ such that } V_1 \cup V_2 = V, V_1 \cap V_2 = \emptyset,\;\text{and}\; \forall\, (u,v) \in E, \; u \in V_1 \text{ and } v \in V_2 \text{ or } u \in V_2 \text{ and } v \in V_1. \)

inputFormat

The input is read from standard input. The first line contains two integers n and m where:

• n is the number of nodes in the graph.
• m is the number of edges in the graph.

The following m lines each contain two integers u and v indicating that there is an edge between node u and node v.

outputFormat

If the graph is bipartite, the output should be as follows:

• The first line contains the string "YES".
• The second line contains two integers representing the size of the first subset and the size of the second subset.
• The third line contains the nodes in the first subset separated by spaces.
• The fourth line contains the nodes in the second subset separated by spaces.

If the graph is not bipartite, output the string "NO" in one line.

## sample

4 4
1 2
2 3
3 4
4 1

YES
2 2
1 3
2 4

</p>