Question

Triology | CodeNation | Coding | OA | SDE | Set-9

Answer 1

Even Paths

You are given a directed acyclic graph with no multiple
edges or self loops.You are given 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 and Y).

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

Input:
First line contains T, the number of test cases
For each test case:
First line contains three space separated integers N, M and X (number of nodes ,number of edges and the source
node respectively)
Next M line contains two space separated integers u and v (there is a directed edge from u to v)

Output:
For each test case:
    A new line containing N space separated integers, where the i-th element is the answer for node i, mod 1000000007

Constraints:
1 <= T <= 20
1 <= N <= 10 5
1 <= M <= min(10 5 , (N*(N-1))/2)
1 <= u, v <= N
1 <= X <= N

Sample Input
2
5 4 1
1 2
2 3
1 4
3 5
5 5 1
1 2
2 3
1 4
3 5
1 5

Sample Output
0 1 0 1 1
0 1 0 1 2