Mrs. Jill is a kindergartener. For the need of a game, she wants to separate all the kids in her class into two groups.

She knows that some kids don't like some of others, so the separation can not place two kids who don't like each other in the same group. It is not a simple task, because Jill even does not know whether the separation is possible. What's worse, Jill must make the difference of the numbers of two group's kids as small as possible, also for the game's sake. In other words, suppose the two group have A and B kids respectively, Jill wants to minimize |A-B|.

Now Jill turns to you, a top coder, for help.


There are multiple test cases, each begins with two integers n and m, 1 <= n <= 1000, which are the number of kids and the number of the kids pair who don't like each other respectively.

Then m lines follow. Each line contains two integers a and b, which means kid a and kid b don't like each other. (All the kids are numbered from 1 to n )

n=m=0 means the end of input.


For each test case output an integer. If it's impossible to separate the kids, output -1. Otherwise output the possible minimum difference of the numbers of kids between two groups.

Sample Input

7 5
1 2
3 4
3 5
3 6
3 7
0 0

Sample Output


Author: zhucheng