Delete and Cut Game
/

## Algorithms, Breadth-first search, Graphs, Probablity

Problem
Editorial
Analytics

You are given a connected graph with $N$ nodes and $M$ edges. Two players $A$ and $B$ are playing a game with this graph. A person $X$ chooses an edge uniformly, randomly, and removes it. If the size (number of nodes in component) of two non-empty connected component created are EVEN, then $A$ wins otherwise player $B$ wins.

Find the probability of winning the game for $A$ and $B$. The probability is of the $\frac P Q$ form where $P$ and $Q$ are both coprimes. Print $PQ^{-1}\ modulo\ 1000000007$.
Note: $X$ can only select the edges which divide the graph into two non-empty connected components after they are removed. If no such edge is present in the graph, then the probability to win can be 0 for both $A$ and $B$.

Input format

• The first line contains two space-separated integers $N\ M$ denoting the number of nodes and edges.
• The next $M$ lines contain two space-separated integers $u\ v$ denoting an edge between node $u$ and node $v$.
Note: The graph does not have multiple edges between two vertices

Output format
Print two space-separated integers denoting the probability of winning for $A$ and $B$ respectively.

Constraints
$1 \le N,\ M \le 1e5$

SAMPLE INPUT
6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4

SAMPLE OUTPUT
0 1
Explanation

X can choose only edge 1-4 and B wins in that case.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...