#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define endl "\n" #define int long long const int N = 2e5 + 5; const int MOD = 1e9 + 7; int n, m, x; int cache[N][2]; vector<int> g[N]; int dp(int idx, int parity) { if(idx == x) return (parity == 1); int &ans = cache[idx][parity]; if(ans != -1) return ans; ans = 0; for(auto &it:g[idx]) ans += dp(it, parity ^ 1); ans %= MOD; return ans; } int32_t main() { IOS; int t; cin >> t; while(t--) { memset(cache, -1, sizeof(cache)); cin >> n >> m >> x; for(int i = 1; i <= n; i++) g[i].clear(); for(int i = 1; i <= m; i++) { int u, v; cin >> u >> v; g[v].push_back(u); //Building reverse graph for easier answer computation } for(int i = 1; i <= n; i++) cout << dp(i, 0) << " "; cout << endl; } return 0; }