Resetting the Baggage Conveyor System

This problem is adapted from PA 2022 Round 5 Walizki.

Imagine you have just checked in at an airport. Have you ever wondered where your suitcase goes? Behind a curtain lies a huge hall containing a number of platforms connected by one‐way conveyor belts. Every piece of luggage initially arrives at platform 1. On each platform, there may be several outgoing conveyors. Note that a conveyor belt from platform i may only lead to a platform with a strictly larger number than i.

If a platform has no outgoing conveyors, a staff member manually takes the luggage from that platform to the corresponding airplane. However, if a platform has several outgoing conveyors, the order in which the belts are listed is important: the first suitcase arriving at that platform leaves via the first conveyor, the second suitcase via the second conveyor, and so on. When a suitcase departs via the last conveyor belt, the next suitcase will go through the first conveyor (i.e. the selection is cyclic).

It is important that when a suitcase is dispatched from a platform, all transfer operations (on the conveyor system or by the staff) are finished before the next suitcase is put on platform 1. In other words, at any given moment, there is at most one suitcase in transit.

It turns out that after processing a certain number of suitcases the system resets: namely, every platform with outgoing conveyors is back to the state where the next arriving suitcase will depart via its first conveyor. Byteasar wants to determine the minimum number of suitcases that must be processed for this to happen. Help him compute this value!

Note: For every platform that has outgoing conveyors, the platform keeps an internal pointer specifying which conveyor will be used for the next suitcase. Every time a suitcase is processed at that platform, the pointer advances cyclically. The system is said to have reset when, for every platform with one or more conveyors, the pointer is back to the beginning (i.e. it is ready to dispatch the next suitcase along its first outgoing belt).

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10⁵) — the number of platforms. The next n lines describe the platforms in order from 1 to n. The i-th line starts with an integer k (0 ≤ k ≤ 10), which is the number of outgoing conveyors from platform i. If k > 0, it is followed by k integers, each representing the destination platform of a conveyor belt. It is guaranteed that every conveyor goes from platform i to some platform j with j > i.

outputFormat

Output a single integer: the minimum number of suitcases that must be processed so that for every platform with outgoing conveyors the pointer has returned to the beginning (i.e. such that the number of suitcases passing through that platform is a multiple of the number of its conveyors).

sample

3
1 2
1 3
0

1