Problem Description

wgr is the commander-in-chief of the $R$ nation's army. Now, he decides to organize two teams to execute two secret missions.

wgr will dispatch $N$ soldiers to carry out these missions, numbered from $1$ to $N$. Due to the critical nature of the missions, wgr needs to ensure that the dispatched teams have absolute coordination. Absolute coordination means that any two soldiers in the team are well-coordinated. Additionally, he needs to minimize the difference in combat power between the two teams. The combat power of a team is defined as $F=2^k$, where $k$ is the number of soldiers in the team, and no soldier should be left out.

wgr already knows which soldiers are well-coordinated, but due to the urgency, he doesn't have time to sort out the information. Now, he asks you to help him organize the information as quickly as possible and tell him:

1. The total number of different grouping plans. Two plans are considered different if and only if the difference in combat power between the two teams is different.
2. The smallest combat power difference among all grouping plans. Since this difference may be very large, output it modulo $10^9+7$.
3. How many pairs of soldiers are well-coordinated but cannot be placed in the same group.

Note: Specifically, due to the importance of team coordination, a team with $N$ soldiers and another team with $0$ soldiers is also a valid grouping plan.

Input Format

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

The next $M$ lines each contain two positive integers $x$ and $y$, indicating that the soldier numbered $x$ is well-coordinated with the soldier numbered $y$.

Output Format

Output consists of two lines.

The first line, if there is a valid plan, output two numbers, the number of grouping plans and the smallest combat power difference modulo $10^9+7$; if there is no valid grouping plan, output one number $-1$.

The second line, output an integer indicating how many pairs of soldiers are well-coordinated but cannot be placed in the same group.

Sample Input and Output

Sample Input #1

4 4
3 4
1 2
2 4
2 3

Sample Output #1

2 0
0

Sample Input #2

10 2
1 7
3 5

Sample Output #2

-1
2

Notes/Hints

This problem consists of three Subtasks.

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

For all data, the same relationship will not be repeated, $1 \leq x, y \leq n$ and $x \neq y$. Additionally, it is guaranteed that $0 \leq m \leq n \times (n-1)/2$.

This problem has a Special Judge:

• If your answer for the first line is correct, you can get $60\%$ of the points for that test case;
• If your answer for the second line is correct, you can get $40\%$ of the points for that test case.

To ensure you can get partial points, please output strictly in the required format.

见题面 Input 部分

见题面 Output 部分