Counting Road Construction Schemes in Fantasy Land

After coming to power, Youxiang's first initiative is to build highways in Fantasy Land. There are n cities in Fantasy Land with no roads at first, and Youxiang promises to lower taxes. So she intends to construct exactly n-1 roads so that all cities are connected. At the same time, there are exactly n-1 construction companies; each company has declared the set of roads (i.e. pairs of cities) it is capable of building. Youxiang plans to:

1. Select n-1 roads from the union of all companies’ able roads such that the chosen roads form a spanning tree (i.e. they connect all n cities and do not form a cycle).
2. Assign each of the chosen roads to a distinct construction company that is capable of building that road.

Two schemes are considered different if either the set of chosen roads is different, or the assignment between roads and companies is different. Output the total number of possible schemes modulo \(998244353\).

Note: In every scheme each construction company builds exactly one road, and every chosen road must be built by a company that has the ability to construct it.

inputFormat

The first line contains an integer n (2 \(\le n \le 10\)), the number of cities.

Then follow n-1 lines describing the construction companies. The i-th of these lines begins with an integer k_i indicating the number of road projects company i can build, followed by 2*k_i integers. Each pair of integers u and v (1 \(\le u, v \le n\), \(u \neq v\)) represents a road between city u and city v that the company is capable of constructing. All roads are undirected. It is guaranteed that there is at least one scheme that connects all cities.

outputFormat

Output a single integer: the number of schemes modulo \(998244353\).

sample

2
1 1 2

1