Department Assignment

A company wants to assign N new employees to two development departments, A and B. Some pairs are friends who must work in the same department, and some pairs are rivals who must work in different departments.

If employees x and y are friends, the relation is written as +(x,y). If they are rivals, it is written as -(x,y). A pair cannot have both relations at the same time. Both relations are symmetric: +(x,y) also means +(y,x), and -(x,y) also means -(y,x).

A valid department assignment must satisfy all of the following conditions.

1. Every new employee is assigned to exactly one of A and B.
2. If +(x,y) holds, x and y must be assigned to the same department.
3. If -(x,y) holds, x and y must be assigned to different departments.
4. Among all assignments satisfying the previous conditions, the difference between the two department sizes must be as small as possible.

For employees {1,2,3}, if their relations are R1 below, all three employees may be assigned to the same department, so a valid assignment exists.

For R2, one valid assignment is A={1,2}, B={3}. For R3, all three pairs are rival pairs, so with only two departments at least one rival pair must end up in the same department. For R4, the friend and rival requirements also conflict, so no valid assignment exists.

When there are 4 employees, both R5 and R6 below are valid. In R5, the minimum difference between department sizes is 2. In R6, the two departments can have the same size, so the difference is 0.

Using the given friend and rival relations, determine for each test data set whether a valid department assignment is possible.

The input always contains 5 test data sets.

For each test data set, the first line contains the number of new employees N and the number of relation records M, separated by a space. Employees are numbered from 1 to N.

Each of the next M lines describes one relation in the form 1 x y or -1 x y. 1 x y means x and y are friends, and -1 x y means x and y are rivals.

N and M are integers between 3 and 10,000, inclusive.

Print one line for each of the 5 test data sets.

If a valid department assignment is possible, print the minimum possible difference between the two department sizes as a non-negative integer. If it is impossible, print -1.