#include #include #include #include #include #include using namespace std; using Modint = atcoder::modint998244353; struct MidData{ int root; Modint reach; Modint pass; }; // - - // | | // -x->-y- MidData rake(MidData x, MidData y){ MidData res; res.root = x.root; res.pass = x.pass * y.pass; res.reach = x.pass * y.reach + x.reach; return res; } MidData compress(MidData x, int newRoot){ MidData res; res.root = newRoot + 1; res.pass = Modint(newRoot + 1); res.reach = Modint(newRoot + 1) * x.reach; return res; } MidData newTree(int newRoot, bool base){ MidData res; if(base){ res.root = 1; res.pass = Modint(0); res.reach = Modint(1); } else { res.root = newRoot + 1; res.pass = Modint(1); res.reach = Modint(0); } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector> edges(N*2); vector xoredges(N-1); for(int i=0; i> c; for(int j=0; j> e; e--; xoredges[e] ^= i; edges[i].push_back(e); } } for(int i=0; i parent(N*2, -1); vector bfs = {0}; for(int i=0; i low(N*2); for(int i=N*2-1; i>=0; i--){ int v = bfs[i]; low[v] = newTree(v, v>=N); int c = edges[v].size(); if(i != 0) c--; for(int j=0; j high(N*2); for(int i=0; i highL(c); vector highR(c); highL[0] = newTree(v, v>=N); if(i != 0){ int w = parent[v]; highL[0] = rake(highL[0], compress(high[v], v)); } for(int t=0; t=N); for(int t=c-1; t>=1; t--){ int w = edges[v][t]; highR[t-1] = rake(compress(low[w], v), highR[t]); } for(int t=0; t ans(N); for(int i=0; i