Background

Snow flies across the sky as arrows shoot at the white deer; smiling, I write of heroes leaning on green mandarin ducks.

In memory of Mr. Jin Yong.

However, this has nothing to do with this problem.

Problem Description

wgr is the commander-in-chief of the army of country $R$. Now, he decides to organize two squads to carry out two secret missions.

wgr will send $N$ soldiers to do these two missions, numbered $1 \sim N$. Since the missions are extremely important, wgr needs the dispatched squads to have perfect cooperation. Perfect cooperation means that any two soldiers within the same squad cooperate well with each other. At the same time, he wants the difference in combat power between the two squads to be as small as possible. The combat power of a squad is defined as $F=2^{k}$, where $k$ is the number of soldiers in the squad. No one is allowed to be left unassigned.

wgr already knows which pairs of soldiers cooperate well, but due to time pressure, he cannot organize the information carefully. He asks you to help him finish organizing the information as fast as possible, and tell him:

1. How many different grouping plans are there in total. Two plans are considered different if and only if the difference in combat power between the two squads is different.
2. Among all grouping plans, what is the minimum combat power difference. Since this difference may be very large, output it modulo $10^9+7$.
3. How many pairs of soldiers cooperate well but can never be assigned to the same squad.

Note: In particular, since squad cooperation is extremely important, a plan where one squad has $N$ soldiers and the other squad has $0$ soldiers is also a valid grouping plan.

Input Format

The first line contains two positive integers $N,M$.

The next $M$ lines each contain two positive integers $x,y$, meaning that soldier $x$ and soldier $y$ cooperate well with each other.

Output Format

Output consists of two lines.

On the first line, if there exists a valid plan, output two numbers: the number of grouping plans and the minimum combat power difference modulo $10^9+7$. If no valid plan exists, output a single number $-1$ on the first line.

On the second line, output one integer: the number of pairs of soldiers who cooperate well but can never be assigned to the same squad.

4 4
3 4
1 2
2 4
2 3

2 0
0

10 2
1 7
3 5

-1
2

Hint

This problem has three subtasks.

• Subtask 1: $5$ test points, $5$ points each, with $N \le 30$.
• Subtask 2: $3$ test points, $10$ points each, with $N \le 300$.
• Subtask 3: $3$ test points, $15$ points each, with $N \le 2500$.

For all testdata, the same relationship will not be given repeatedly. $1 \le x,y \le n$ and $x \neq y$. Also, it is guaranteed that $0 \le m \le n \times (n-1)/2$.

This problem uses a Special Judge.

• If the output on the first line is correct, you can get $60\%$ of the score for that test point.
• If the output on the second line is correct, you can get $40\%$ of the score for that test point.

To make sure you can get partial points, please output according to the required format.

Translated by ChatGPT 5