Given graph with N vertices and M edges. You need to find if there is a way to partition the graph in two parts in such a way that these parts are connected with m/2 edges. Division is integer division. If there is solution print it out, else print -1. Input: first two numbers are N and M. Next M lines are pairs of integers (X,Y) representing edge between vertices X and Y. Output: If there is no solution, print -1. Else, in the first line print size of two groups (N1,N2) , in second line print N1 numbers representing vertices in first group, same for second group.

5<= N <= 1000
1<= M <= 10000
TL : 0.2s
ML : 64MB

Input:
8 10
1 2
1 5
1 6
5 6
2 6
3 8
3 7
3 4
4 8
7 8

Output:
4 4
5 6 7 8
1 2 3 4

Your help would be appreciated.