SOLVE

LATER

Delete and Cut Game

/

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\)

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

Initializing Code Editor...