Teams

Time limit1sMemory limit128 MB

Summary

Count ways to split N players into two equal-size teams so that no player shares a team with anyone on his exclusion list, treating the two teams as unordered.

Level: Medium6 of 10
Topics: Union-find, Combinatorics, Graph
Solved: No attempts yet

Problem

Friends from the neighbourhood gathered on the school playground to play a football match, and they must be divided into two teams. The players wear T-shirts numbered 1 to N, assigned so that the best player has number 1 and the worst player has number N.

The two teams must have an equal number of players. Each player writes a list of the colleagues he does not want on his own team. Since everyone would rather play alongside stronger players, each player's list contains only players who are worse than he is (that is, players with larger numbers).

A division into two equal teams is valid if, for every player, none of the colleagues on his list end up on his team. Count how many different valid divisions exist.

Input

The first line contains an even integer N (2 ≤ N ≤ 1000), the number of friends.

Each of the next N lines describes one player's wish-list; the (i+1)-th line describes player i's list in the form:

K A1 A2 ... AK

meaning that player i does not want any of A1, A2, ..., AK on his team. Every listed number is larger than i.

The input is guaranteed to admit at least one valid division.

Output

Print a single integer: the number of different valid divisions into two equal teams. Two divisions are considered the same if they yield the same unordered pair of teams (the two teams are interchangeable).

Examples3

Example 1
Input
```
4
1 4
1 3
1 4
0
```
Expected output
```
1
```
Example 2
Input
```
6
2 3 5
1 4
0
0
1 6
0
```
Expected output
```
2
```
Example 3
Input
```
8
1 5
0
1 7
0
0
0
0
0
```
Expected output
```
12
```