#214843. [ICPC 2021 Seoul R] Friendship Graphs

Given a collection of people who interact, we can define a graph whose vertices are people, with an edge between two people if and only if they are friends with one another. Such graphs are called social networks and are well defined on any set of people, for example, the students in a college or the residents of a small town. An entire science analyzing social networks has sprung up in recent years, because many interesting aspects of people and their behavior are best understood as properties of this friendship graph.

Given a friendship graph where the vertices are the students in the Problem Solving class, your job is to write a program that decomposes the students in the class into two groups, and , so that the following three conditions are satisfied simultaneously:

• Each student in the class belongs to exactly one group, or .
• Any two students in each group are friends with each other.
• The difference between the sizes of groups and , denoted as , is as small as possible.

For example, suppose we are given a friendship graph shown in the figure below. Decomposing the students into and is not possible because and are not friends. On the other hand, in the decomposition into and , any two students in each group are friends with each other; however, the size difference () between the two groups is larger than the difference () in the decomposition into and . The last one is an optimal decomposition we want.

:::align{center} :::

Your program is to read from standard input. The first line contains two integers and , respectively indicating the numbers of vertices and edges of a friendship graph, in which we assume and . The vertices are indexed from to . In the following lines, each line contains two integers and which represent an edge of the graph.

Your program is to write to standard output. Print exactly one line that contains an integer. The integer should be the minimum of the size differences between two groups if the students can be decomposed into two groups satisfying the above three conditions; otherwise, the integer should be .

样例输入 1

7 13
1 2
2 3
3 1
3 4
3 5
3 6
3 7
4 5
5 7
7 6
6 4
4 7
5 6

样例输出 1

1

样例输入 2

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

样例输出 2

-1

样例输入 3

4 4
4 3
3 2
2 1
1 4

样例输出 3

0