Codenation test 21st july graph question help

[avi130698]

Can someone provide the optimized way to solve this? I tried but got 8/16 and tle for rest.
this was my solution ans the question.

#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
    int n,m,x,i,j,u,v;
    cin>>n>>m>>x;
    vector<vector<int> > graph(n);
    for(i=0;i<m;i++){
        cin>>u>>v;
        graph[u-1].push_back(v-1);
    }
    vector<int> ans(n,0);
    queue<int> node;
    queue<int> h;
    vector<int> vis(n,0);
    node.push(x-1);
    h.push(1);

    while(!node.empty()){
        int y=node.front();
        node.pop();
        int w=h.front();
        h.pop();
        //cout<<y<<" | "<<w<<endl;
        if(w%2==0){
            ans[y]++;
        }
        for(i=0;i<graph[y].size();i++){
            node.push(graph[y][i]);
            h.push(w+1);
        }
    }
    //cout<<endl;
    for(i=0;i<n;i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
return 0;
}

[sarthakmanna]

Start a bfs from node X. As you traverse, maintain two dp arrays dpOdd and dpEven. dpOdd[i] = Number of paths starting from X and ending at node i with odd number of vertices in the path. Same for the dpEven array.

Now, as you travel from node i to j, the transition will be
dpOdd[j] += dpEven[i]; dpEven[j] += dpOdd[i]

Obviously, dpOdd[X] = 1; dpEven[X] = 0

Now the actual problem lies in the bfs traversal. You can never move from node i to node j unless the value of dpEven[i] and dpOdd[i] is finalised.

Also, you need to account for the nodes which are unreachable from X. My solution was to first remove the unreachable nodes. You can do it in other ways too.