Extra Judicial Operation

Given a connected undirected graph, find the minimum number of vertices beyond one that must hold servers so every vertex still reaches a server after any single edge is removed.

Hard8GraphDFSBrute forceImplementationNo attempts yetTime limit2sMemory limit512 MB

Problem

A programming contest runs at several sites at the same time. The sites are joined by a network of two way links. Each link joins two different sites, and at most one link joins any pair of sites. Contestants submit their solutions to judging servers. A judging server sits at one site, and a contestant at some site can use that server when the two sites are still joined by working links.

Every contestant must have access to at least one judging server at all times. While every link works, the network joins all sites, so one judging server is enough. At the other extreme, a judging server at every site guarantees access even if every link fails. The organisers want to run as few judging servers as possible without losing that guarantee.

The network has one reliable property. At any moment exactly one link is broken, and a broken link carries nothing in either direction. Any link can be the broken one. The organisers want the smallest number of judging servers such that, whichever single link is broken, every site still reaches at least one judging server.

They already know that they must run at least one judging server. Report how many extra judging servers they must run beyond that first one.

Input

The first line contains one integer SS (2S1000002 \le S \le 100\,000), the number of sites. The sites are numbered 00 to S1S-1.

The next SS lines describe the sites in order, starting with site 00. The line for site ii starts with an integer kik_i (0ki<S0 \le k_i < S), the number of links from site ii to a site with a larger number. Then follow kik_i integers in ascending order, the sites those links go to. A link is two way, but it appears only on the line of its lower numbered site. The total number of links is at most 100000100\,000, and the links join all SS sites into one network.

Output

Print the minimum number of extra judging servers the organisers must run.