1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 100005;
const int maxk = 55;

mt19937 rd;
int grd(int l, int r) {
    return rd() % (r - l + 1) + l;
}
#define vec array<int, maxk>

struct bin {
    vec a[maxk];
    ll inv[maxk];
    int rk;
    bin() {
        rk = 0;
    }
    bool ins(vec x) {
        for (int i = 0; i < maxk; i++) 
            if (x[i]) {
                if (!a[i][i]) {
                    a[i] = x;
                    inv[i] = ksm(x[i], mod - 2);
                    rk += 1;
                    return 1;
                }
                else {
                    ll bk = x[i] * inv[i] % mod;
                    for (int j = i; j < maxk; j++)
                        x[j] = (x[j] - a[i][j] * bk) % mod;
                }
            }
        return 0;
    }
}r[maxk];
int pl[maxk];
vi eg[maxn];
vec cur[maxn];
int fl[maxn];
ll ans[maxk];
void cal(int a) {
    if (fl[a]) return ;
    fl[a] = 1;
    for (int i = 0; i < maxk; i++) cur[a][i] = 0;
    for (auto v : eg[a]) {
        cal(v);
        ll t = grd(1, mod - 1);
        for (int i = 0; i < maxk; i++)
            cur[a][i] = (cur[a][i] + t * cur[v][i]) % mod;
    }
}
int main() {    
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) 
        for (int j = 0; j < maxk; j++)
            cur[i][j] = grd(1, mod - 1), fl[i] = 1;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        eg[v].pb(u);
    }
    for (int i = 1; i <= n; i++)
        cal(i);
    for (int i = 0; i < maxk; i++)
        pl[i] = k;
    int cnt = 1;
    for (int i = k + 1; i <= n; i++) {
        for (int j = cnt - 1; j >= 0; j--) {
            if (j == cnt - 1) pl[j] = i;
            int cr = r[j].ins(cur[i]);
            if (!cr) {
                for (int u = j; u < cnt; u++)
                    r[u] = r[u + 1], pl[u] = pl[u + 1];
                cnt -= 1;
                break;
            }
        }
        for (int m = 0; m < cnt; m++) {
            int ls = k; if (m) ls = pl[m - 1];
            ans[r[m].rk] += pl[m] - ls;
        }
        int ff = k;
        if (cnt) ff = pl[cnt - 1];
        ans[0] += i - ff;
        for (int j = cnt; j < maxk; j++)
            pl[j] = k;
        r[cnt] = r[cnt + 1];
        cnt += 1;
    }
    for (int i = 0; i <= k; i++)
        cout << ans[i] << endl;
    return (0-0); 
}