Walcott and Equivalence Relation
Walcott has a set of N numbers, 0 to N-1. He defines a relation R on this set. His friend Sanchez wants to make it an equivalence relation.
For that he adds least number of extra relations to make it an equivalence relation.
Walcott picks a set of k numbers from his set. What is the probability that in the set of chosen k numbers, no two elements are related to each other?
If p/q is the probability the answer is (p/q)% 10^9.
Note 1: It is guaranteed the maximum possible set that can be obtained such that no two elements of the set are related is of size less than 3*10^3.
Note 2: You will be given the relations that Walcott originally defined and not that Sanchez added.
First line contains N,r and k.
Then r lines follow containg two numbers, denoting a relation.
Print Answer for each test case on a single line.
2 <= N <= 10^5
1 <= r <= 10^5
1 <= k <= min(3*10^2,N)
5 2 5
There is only one way to choose 5 elements from a set of 5 elements
But in this set 1 and 3 are related to each other. So, For there is no such set of size k=5.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.