Bipartite Graph Partitioning

You are given an undirected graph with \(N\) nodes and \(M\) edges. Your task is to determine whether the graph is bipartite. A graph is bipartite if its vertices can be divided into two disjoint sets \(S_1\) and \(S_2\) such that every edge connects a vertex in \(S_1\) to one in \(S_2\). Formally, there exists a function \(f: V \to \{0,1\}\) such that for every edge \((u,v)\), \(f(u) \neq f(v)\).

If the graph is bipartite, output the two sets of vertices in sorted order (each set on its own line). If one of the sets is empty, output an empty line for that set. If the graph is not bipartite, simply output Not Bipartite.

Note: The vertices are numbered from 1 to \(N\). In the case of isolated vertices (with no edges), assume they belong to the first set.

inputFormat

The input is given via stdin and has the following format:

N M
u1 v1
u2 v2
...
 uM vM

Here, \(N\) is the number of nodes, \(M\) is the number of edges, and each of the next \(M\) lines contains two integers \(u\) and \(v\) representing an undirected edge between nodes \(u\) and \(v\).

outputFormat

If the graph is bipartite, print two lines. The first line contains the vertices in the first set in increasing order, separated by spaces, and the second line contains the vertices in the second set in increasing order, separated by spaces. If a set is empty, print an empty line for that set. If the graph is not bipartite, output just Not Bipartite.

## sample

6 6
1 2
2 3
3 4
4 5
5 6
6 1

1 3 5
2 4 6

</p>