Sibling Problem

0

0 votes
maths, Graph, Medium
Problem

There are N kids in the park. Some of these kids are sibling to each other. You are given some of the sibling pairs, ie, 'a' is sibling of 'b'. Also, using these given pairs, you can form all the sibling pairs in the park using the property that if 'a' is sibling of 'b' and 'b' is sibling of 'c', then 'a' is sibling of 'c'. It is garanteed that using the given pairs, one can form all the valid pairs present in the park.

Your task is to calculate the probability that if we randomly select a pair of kids, they will not be siblings. If the answer is P/Q, print (PQ1)modulo(109+7).

Note: Pairs (a, b) and (b, a) are same.

Input Format:

First line contains N and M, number of kids and number of sibling pairs given respectively.

Each of the next M lines contains A and B, denoting that A is a sibling of B.

Output Format:

Print the probability in format (PQ1)modulo(109+7).

Constraints:

1N,M106

1A,BN

AB

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are 4 kids. It is given that 1 is sibling of 2 and 2 is sibling of 3. The only pairs that are not sibling are (1, 4), (2, 4), (3, 4). Total pairs are 6. Hence, probablity is 1 / 2.

Editor Image

?