This is a graph problem from the previous contest by Codenation .

Can you suggest some ideas to approach it or sketch the solution ?

Problem :- You are given a DAG(Directed A-cyclic Graph)

You are also given a source node- 'X' as input .

For each node 'Y' , find the number of paths that start at 'X' and end at 'Y' , such that the number of nodes visited along that path is even(including X an Y)

Note:- The path from X to X consists of only one node and hence the number of the nodes visited is odd. Hence there are 0 paths for X to X which consist of even number of nodes.

The number of test-cases:- 20

Number of nodes in the graph(n):- 100000.

Edges:- [1,minimum(100000,n*(n-1)/2]

Output:-'n' space separated integers such that the i'th element is the answer for node 'i', mod 1000000007

Thanks :-)