Bipartite Graph Partition Problem

You are given an undirected graph with n vertices and m edges. Your task is to determine whether the graph is bipartite. A graph is bipartite if its vertex set V can be partitioned into two disjoint subsets such that no edge connects vertices within the same subset. Equivalently, a graph G = (V, E) is bipartite if and only if it is 2-colorable, i.e., there exists a function \(f: V \to \{0, 1\}\) satisfying \(f(u) \neq f(v)\) for every edge \((u,v) \in E\).

If the graph is bipartite, output the size and the sorted list of vertices in each of the two sets. Otherwise, output -1.

inputFormat

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

n m
u1 v1
u2 v2
... 
um vm

Here, the first line contains two integers n and m indicating the number of vertices and edges, respectively. Each of the next m lines contains two integers u and v representing an edge between vertices u and v (vertices are numbered from 1 to n).

outputFormat

If the graph is bipartite, print four lines:

• The first line contains the number of vertices in the first set.
• The second line contains the sorted list (in ascending order) of vertices in the first set, separated by spaces.
• The third line contains the number of vertices in the second set.
• The fourth line contains the sorted list (in ascending order) of vertices in the second set, separated by spaces.

If the graph is not bipartite, simply output -1 in one line.

## sample

4 4
1 2
1 3
2 4
3 4

2
1 4
2
2 3

</p>