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 \(a/b\) can be represented as \(p/q\) such that \(gcd(p,q) = 1\) where \(gcd\) is greatest common divisor.

For example , reduced form of fraction \(2/4\) is \(1/2\).

A fraction \(a/b\) is called good fraction if its reduced form \(p/q\) satisfies the following conditions :

• Both \(p\) and \(q\) are odd.
• \(p\leq q\)

For example , some of the good fractions are \((1/3),(2/2),(2/6),...\)

but \((2/5),(4/10),(3/1)\) are not good fractions.

Now, Mr.A was given an undirected graph with \(N\) nodes and \(M\) 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 \(i\) ,

Let \(s\) be set of numbered/indexed nodes which are not adjacent to node \(i\) .

Calculate number of good fractions \(a/b\) where \(1\leq a \leq N\) and \(1 \leq b \leq N\) such that their reduced form \(p/q\)  satisfies the following conditions , 

• \(q = i\)
• \(p\) must be element of set \(s\) .

Mr. A is stuck in this task, please help him.

Example

Consider n = 3, m = 1.
Edges:

• 2 3

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.

• n: Represents the number of nodes
• m: Represents the number of edges
• edges: Represents the connection between nodes

Input Format:

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• First line contains \(T\) which denotes number of test cases. For each test case,
  • First line contains \(N\) and \(M\).
  • \(M\) lines follow, each contains two numbers \(a\) and \(b\) denoting edge between them.

Output Format:

For each node \(i\) , print the output as mentioned above.

Constraints:

\(1\leq T \leq 5\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.