All Tracks Algorithms Graphs Breadth First Search Problem

Delete and Cut Game
Tag(s):

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Circuits '20

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?