Mr.A was studying about fractions in his mathematics lecture. He learned that every fraction can be represented in reduced form.
A reduced form of fraction can be represented as such that where is greatest common divisor.
For example , reduced form of fraction is .
A fraction is called good fraction if its reduced form satisfies the following conditions :
For example , some of the good fractions are
but are not good fractions.
Now, Mr.A was given an undirected graph with nodes and edges. The given graph does not have any multiple edges or self loops.
Now, task assigned to Mr.A was to find answer for every node ,
Let be set of numbered/indexed nodes which are not adjacent to node .
Calculate number of good fractions where and such that their reduced form satisfies the following conditions ,
Mr. A is stuck in this task, please help him.
Example
Consider n = 3, m = 1.
Edges:
You must determine the output as mentioned above.
The output is 0 0 1.
For node 1: 0
set s is (2,3)
(2/2),(3/3)... are good fractions but in their reduced form, it becomes (1/1) but the numerator is not present in set (s).
For node 2: 0
As q is even
For node 3: 1
set s is (1)
(1/3) is the only good fraction.
Function description
Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the output as mentioned above.
Input Format:
Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).
Output Format:
For each node , print the output as mentioned above.
Constraints:
Code snippets (also called starter code/boilerplate code)
This question has code snippets for C, CPP, Java, and Python.
For node
set is
are good fractions but in their reduced form , it becomes but numerator is not present in set .
For node
set will be
are only good fractions satisfying.
are also good fractions but after reducing it , it becomes but and do not belong to set .