#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n, maxnights, h;
cin >> n >> maxnights >> h;
vector<ll> vis(n), depth(n, -1e8);
vector<vector<pair<ll, ll>>> adj(n), radj(n);
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < h; j++) {
ll a, b;
cin >> a >> b;
adj[i].push_back({a, b});
radj[a].push_back({i, b});
}
}
depth[n - 1] = 0;
auto dfs = [&](auto &&self, ll u) {
if (vis[u])
return;
vis[u] = 1;
for (auto [x, y] : radj[u]) {
if (vis[x])
continue;
self(self, x);
}
};
dfs(dfs, n - 1);
map<ll, ll> m;
auto dfs1 = [&](auto &&self, ll u, ll stay) {
if (stay >= maxnights)
return;
if (u == n - 1) {
m[stay] = min(500000000LL, m[stay] + 1);
return;
}
if (vis[u] == 0 or vis[u] == 2)
return;
vis[u] = 2;
for (auto [x, y] : adj[u]) {
if ((vis[x] == 1 and x > u)) {
for (int l = y; stay + l < maxnights; l++)
self(self, x, stay + l);
}
}
vis[u] = 1;
};
dfs1(dfs1, 0, 0);
for (auto [x, y] : m) {
cout << y << "\n";
}
}
