P4336 [SHOI2016] Gensokyo Before the Dark

The quadrennial Gensokyo election has begun. Recently, the biggest problem in Gensokyo is that many mysterious youkai have flooded in, disrupting its former order. However, the establishment youkai (and humans) such as Reimu Hakurei and Yukari Yakumo keep talking about equality for all youkai and diversity in Gensokyo, while offering no reasonable solutions to the pressing issues Gensokyo now faces. Yuuka Kazami is one of the few great youkai in Gensokyo who realized the severity of the problem. She bravely stepped up to run in the election, proposing a series of plans such as building a wall on Gensokyo’s border (and making humans pay for it) and vigorously promoting infrastructure to reduce unemployment. She became the unexpected dark horse of the election year and successfully became the leader of Gensokyo.

After taking office, Yuuka’s first measure is to build Gensokyo’s highways. There are $n$ cities in Gensokyo, and initially there are no roads. Yuuka promised voters to cut taxes, so she plans to build only $n - 1$ roads to connect all these cities. There are exactly $n - 1$ construction companies, and each company wants to gain some benefits during road construction. Although these companies did not give Yuuka money before the election, she still intends to maintain good relations with them, since she is counting on them to help her build the wall. So she plans to have each construction company be responsible for exactly one road. Each construction company has told Yuuka between which pairs of cities it is capable of building a road. Yuuka will choose $n - 1$ edges that can connect all cities in Gensokyo, then assign each edge to a construction company that can build it, with each company building exactly one edge. Yuuka now wants to know how many possible schemes there are in total. Two schemes are different if and only if either the set of edges to be built is different, or the assignment of companies to edges is different.

The first line contains an integer $n$, the number of cities. Lines $2$ through $n$: line $i + 1$ describes the list of roads that the $i$-th construction company can build. It starts with a non-negative integer $m_i$, the number of roads it can build; then follow $m_i$ pairs of integers $u, v$, each pair denoting the endpoints of an edge. Within a company’s list, there are no duplicate edges and no self-loops.

Output a single integer on one line: the number of all possible schemes modulo $10^9+7$.

Constraints - For $20\%$ of the test points, $n \le 5$. - For $50\%$ of the test points, $n \le 8$. - For $60\%$ of the test points, $n \le 10$. - For $100\%$ of the test points, $2 \leq n \le 17$, $0 \leq m_i \leq \frac{n(n - 1)}{2}$, $1 \leq u, v \leq n$. Translated by ChatGPT 5