去年的赛场上，我写了一段愚蠢的代码，民间数据90分，结果最后50...

而今，在我早上又一次被CCF的良心打击到、晚上准备“洗雪耻辱”之时，却发现自己

无论用long long还是__int128都是60'

求助解决方案

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
template<typename T> T gcd(T m, T n) { while (n != 0) { T t = m % n; m = n; n = t; } return m; }
template<typename T> T lcm(T m, T n) { return m / gcd(m, n) * n; }
template<class Integer>
struct Frac {
	Integer p, q;
	Frac(Integer a = 0, Integer b = 1) {
		if(!b) b = 1;
		p = a, q = b;
	}
	Frac(const Frac& x) { p = x.p; q = x.q; this->simplify(); }
	Frac operator = (const Frac& x) { p = x.p; q = x.q; return *this; }
	void simplify() {
		if(!p) { q = 1; return; }
		Integer tmod = gcd(p, q);
		p /= tmod; q /= tmod;
	}
	Frac operator + (const Frac& x) const {
		#ifdef debug
		cout << this->p << '/' << this->q << " + " << x.p << '/' << x.q << " = ";
		#endif
		Frac th = *this;
		th.simplify();
		int down = lcm(th.q, x.q);
		int p1 = th.p * (down / th.q),
			p2 = x.p * (down / x.q);
		Frac res = Frac(p1 + p2, down);
		res.simplify();
		#ifdef debug
		cout << res.p << '/' << res.q << endl;
		#endif
		return res;
	}
	Frac operator * (Integer x) const {
		Frac th = *this;
		th.simplify();
		Frac res = Frac(th.p * x, th.q);
		res.simplify();
		return res;
	}
	Frac operator * (Frac x) const {
		Frac th = *this;
		th.simplify();
		Frac res = Frac(th.p * x.p, th.q * x.q);
		res.simplify();
		return res;
	}
};
typedef Frac<long long> Real;
int n, m, cnt_in[N], cnt_out[N];
vector<int> e[N];
Real vol[N];
vector<pair<int, Real> > ans;
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++ ) {
		int tmp; scanf("%d", &tmp);
		for(int j = 1; j <= tmp; j ++ ) {
			int tt; scanf("%d", &tt);
			e[i].push_back(tt);
			cnt_out[i] ++ ; cnt_in[tt] ++ ;
		}
	}
	#ifdef debug
	for(int i = 1; i <= n; i ++ ) cout << cnt_in[i] << " ";
	cout << endl;
	for(int i = 1; i <= n; i ++ ) cout << cnt_out[i] << " ";
	cout << endl << endl;
	#endif
	queue<int> Q;
	for(int i = 1; i <= n; i ++ ) if(!cnt_in[i]) { vol[i] = Real(1, 1); Q.push(i); }
	while(!Q.empty()) {
		#ifdef debug
		auto QQ = Q;
		printf("queue: ");
		while(!QQ.empty()) { cout << QQ.front() << " "; QQ.pop(); }
		cout << endl;
		cout << "volume: ";
		for(int i = 1; i <= n; i ++ ) cout << vol[i].p << '/' << vol[i].q << " ";
		cout << endl;
		#endif
		int u = Q.front(); Q.pop();
		if(!cnt_out[u]) { ans.push_back(make_pair(u, vol[u])); continue; }
		Real next_flow = vol[u]; next_flow.q *= e[u].size();
		#ifdef debug
		cout << "next: " << next_flow.p << '/' << next_flow.q << endl;
		#endif
		next_flow.simplify();
		vol[u] = 0;
		for(unsigned i = 0; i < e[u].size(); i ++ ) {
			int v = e[u][i];
			vol[v] = vol[v] + next_flow;
			cnt_in[v] -- ;
			if(!cnt_in[v]) Q.push(v);
		}
	}
	sort(ans.begin(), ans.end(), [](pair<int, Real> a, pair<int, Real> b) -> bool {
		return a.first < b.first;
	});
	for_each(ans.begin(), ans.end(), [](pair<int, Real> x) {
		printf("%lld %lld\n", x.second.p, x.second.q);
	});
	return 0;
}