It can be solved using DP. Build up adjacency list for the graph and an adjacency list for the reverse graph. Then, maintain a memoization table to store the no of even and odd paths from source till every vertex v. Now, looping over all the vertices who haven't been visited yet and are sink vertices(outdegree = 0) call a recursive function.

No of even length paths till vertex v = No of odd length paths till all the vertices that have an outgoing edge to v. 

Similarly, compute the odd length paths. I think this should work.

Brief solutions: evenpaths: for each node try to count odd and even length paths using info of nodes that have a edge going into current node in a dp style.

Constraint gcd: hint : for each segment try to reduce it to counting walka in a suitable graph after which it is matrix expo

Divisor luck: for each number get its sum of divisors. After that process in sorted order.

How about the following solution to the problem 3 - Taking the node x as src, start dfs and have a parameter in the dfs function which will increase by one with every recursive call of dfs, whenever that parameter is odd, we increment that current node value by one. At end we just print out the values associated with all the nodes.

Here is the code, It passed all the test cases.

Code Speaks for itself, but feel free to ask doubts.

Knowledge required for this is Dp on trees and Topological Sort.

//Optimise
#include <bits/stdc++.h>
using namespace std;

#define multitest 1
#ifdef Debug
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__);
template <typename Arg1>
void ZZ(const char *name, Arg1 &&arg1)
{
	std::cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void ZZ(const char *names, Arg1 &&arg1, Args &&... args)
{
	const char *comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}
#else
#define db(...)
#endif

using ll = long long;
#define f first
#define s second
#define pb push_back
const long long mod = 1000000007;
auto TimeStart = chrono::steady_clock::now();

const int nax = 2e5 + 10;

void solve()
{
	int n, m, x;
	cin >> n >> m >> x;
	vector<vector<int>> Adj(n + 1), indegree(n + 1);
	int u, v;
	for (int i = 0; i < m; ++i)
	{
		cin >> u >> v;
		Adj[u].pb(v);
		indegree[v]++;
	}
	vector<int> Oddways(n + 1), Evenways(n + 1);
	queue<int> Q;
	for (int i = 1; i <= n; ++i)
		if (!indegree[i])
			Q, push(i);
	Oddways[x] = 1;
	while (!Q.empty())
	{
		auto top = Q.front();
		Q.pop();
		for (int child : Adj[top])
		{
			Oddways[child] += Evenways[top];
			Evenways[child] += Oddways[top];
			Oddways[child] %= mod;
			Evenways[child] %= mod;
			indegree[child]--;
			if (!indegree[child])
				Q.push(child);
		}
	}
	for (int i = 1; i <= n; ++i)
		cout << Evenways[i] << ' ';
	cout << '\n';
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
	while (t--)
		solve();
#ifdef TIME
	cerr << "\n\nTime elapsed: " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " seconds.\n";
#endif
	return 0;
}