Bipartite Team Partition and Synergy Analysis

Commander wgr of country $R$ must assign $N$ warriors (numbered from $1$ to $N$) into two teams to carry out two secret missions. Due to the extreme importance of these missions, each team must have absolute synergy; that is, for any two warriors in the same team, they must have synergy. The combat power of a team of $k$ warriors is defined as $F=2^{k}$.

In addition, wgr wants the two teams' combat powers to differ by as little as possible. Note that it is allowed to have one team with all $N$ warriors and the other with $0$ warriors.

You are given the synergy information between some pairs of warriors. Two warriors that have synergy are denoted by an edge in the synergy graph $G$. A valid grouping requires that each team is a clique in $G$ (i.e. every two warriors in the same team have synergy). Equivalently, if you define the complement graph $H$ (where an edge between two warriors exists if and only if they do not have synergy), then each team must be an independent set in $H$. Hence, a valid grouping is equivalent to a 2-coloring (bipartition) of $H$.

Your task is to determine the following:

1. The number of different grouping schemes, where two schemes are considered different if and only if the absolute difference in combat power between the two teams is different. (Note that if two different partitions yield the same combat power difference, they are regarded as the same grouping scheme for this count.)
2. The smallest possible combat power difference among all valid grouping schemes. Since this number may be large, output it modulo $10^9+7$.
3. The number of synergy pairs (given in the input) that can never be assigned to the same team in any valid grouping scheme. In a connected component of $H$, the bipartite coloring is unique up to swap; hence if two warriors lie in the same component and their colors are forced to be different, they can never be in the same team. (If the two warriors belong to different components, you may assign them the same color arbitrarily.)

Input Format: The first line contains two integers $N$ and $M$, representing the number of warriors and the number of synergy pairs, respectively. Each of the following $M$ lines contains two integers $u$ and $v$, indicating that warriors $u$ and $v$ have synergy.

Output Format: Print three space‐separated integers, representing:

• The number of distinct grouping schemes (in terms of combat power difference),
• The minimum combat power difference modulo $10^9+7$, and
• The number of synergy pairs that can never be assigned to the same team.

Note: A grouping where one team has $N$ warriors and the other has $0$ warriors is considered valid.

Hint: Since a valid grouping is equivalent to a 2-coloring of the complement graph $H$, you may first build the synergy graph $G$ and use the fact that $H$ is the complement of $G$. Then, work component‑wise. For each connected component of $H$, the bipartite coloring is unique up to swapping the two colors. If a component has parts of sizes $a$ and $b$, its contribution to the team size difference is $a-b$ (or $b-a$). Combine these contributions over all components (by trying both sign choices per component) to get the overall difference in team sizes. Finally, note that if team sizes are $x$ and $N-x$, the combat power difference is \(2^{\max\{x,N-x\}}-2^{\min\{x,N-x\}}\).

inputFormat

The first line contains two integers $N$ and $M$. Each of the next $M$ lines contains two integers $u$ and $v$, representing a synergy pair between warriors $u$ and $v$.

For example:

4 3
1 2
1 3
2 3

outputFormat

Print three space-separated integers: the number of distinct grouping schemes (in terms of the combat power difference), the minimum combat power difference modulo $10^9+7$, and the number of synergy pairs that can never be in the same team.

For example, for the sample input above, the output should be:

1 6 0

sample

1 0

1 1 0

</p>