Bipartite Tree Coloring

You are given a forest containing n trees (nodes) and m connections (edges). Your task is to determine if it is possible to color each tree using exactly two colors such that no two trees directly connected by an edge share the same color.

If it is possible, output two groups of tree indices corresponding to the two colors. Otherwise, output -1.

The problem can be mathematically formulated as checking if the graph is bipartite. Formally, let \(G=(V,E)\) be an undirected graph. Determine whether there exists a partition \(V = V_1 \cup V_2\) such that \(V_1 \cap V_2 = \emptyset\) and for every edge \((u,v)\in E\), either \(u\in V_1, v\in V_2\) or \(u\in V_2, v\in V_1\).

inputFormat

The input is given via standard input (stdin) in the following format:

n m
u1 v1
u2 v2
... 
um vm

Where:

• n is the number of trees (nodes),
• m is the number of connections (edges),
• Each of the next m lines contains two integers \(u\) and \(v\) indicating there is an edge between tree \(u\) and tree \(v\).

outputFormat

If a valid 2-coloring exists, print two lines:

• The first line contains the indices of trees in the first group separated by spaces (in ascending order).
• The second line contains the indices of trees in the second group separated by spaces (in ascending order). If the second group is empty, print an empty line.

If no valid coloring exists, print a single line with -1.

## sample

5 4
1 2
1 3
2 4
3 5

1 4 5
2 3

</p>