排水系统

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct PQ
{
	__int128 p, q; // p/q
};
__int128 gcd(__int128 a, __int128 b)
{
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
__int128 lcm(__int128 a, __int128 b)
{
	return a / gcd(a, b) * b;
}
PQ operator+(const PQ &a, const PQ &b)
{
	__int128 nq = lcm(a.q, b.q);
	__int128 np = a.p * (b.q / gcd(a.q, b.q)) +
				  (a.q / gcd(a.q, b.q)) * b.p;
	PQ res = (PQ){np, nq};
	__int128 d = gcd(res.p, res.q);
	res.p /= d;
	res.q /= d;
	return res;
}
void fixed(PQ &a)
{
	__int128 d = gcd(a.p, a.q);
	a.p /= d;
	a.q /= d;
}
void write(__int128 x)
{
	if (x >= 10)
		write(x / 10);
	cout << (int)(x % 10);
}
int n, m;
int inD[112345];
int outD[112345];
vector<int> e[112345];
PQ ans[112345];
queue<int> q;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int u = 1; u <= n; u++)
	{
		cin >> outD[u];
		for (int j = 1; j <= outD[u]; j++)
		{
			int v;
			cin >> v;
			e[u].push_back(v);
			inD[v]++;
		}
		ans[u] = (PQ){0, 1};
	}
	for (int i = 1; i <= m; i++)
		ans[i] = (PQ){1, 1};
	for (int i = 1; i <= n; i++)
		if (inD[i] == 0)
			q.push(i);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		int num = e[u].size();
		if (num == 0)
			continue;
		PQ temp = ans[u];
		temp.q *= num;
		fixed(temp);
		for (int i = 0; i < e[u].size(); i++)
		{
			int v = e[u][i];
			ans[v] = ans[v] + temp;
			inD[v]--;
			if (inD[v] == 0)
				q.push(v);
		}
	}
	for (int i = 1; i <= n; i++)
		if (outD[i] == 0)
		{
			write(ans[i].p);
			cout << " ";
			write(ans[i].q);
			cout << "\n";
		}
	return 0;
}