15147번 - Extra Judicial Operation 다국어

The Suitably Protected Programming Contest (SPPC) is a multi-site contest in which contestants compete at specified sites, which are linked by the Notorious Broken Network (NBN) of two-way links between some pairs of individual sites. There is at most one link directly between any pair of sites and there is no link from a site to itself. Contestants submit their solutions to a judging server to get them tested. The event will use one or more judging servers. Each judging server is located at a contest site and may be accessed directly from that site or through a sequence of linked sites.

At any time during the contest, each contestant must have access to at least one judging server. The links between sites are set up in such a way that if all links work properly, it would suffice to operate one judging server. At the other extreme, having each site operate its own judging server would guarantee access even if all of the links failed. The organisers wish to minimise the number of judging servers that they operate, while still maintaining the integrity of the contest.

Examination of the NBN’s performance over time reveals some good news. The NBN is reliably unreliable! At any given time, exactly one link is broken (that is, communications cannot travel in either direction on that link). Given this fact, the organisers want you to work out the minimum number of judging servers that must operate so that no matter which link is broken, every contestant still has access to at least one judging server.

As they know that they must operate at least one judging server, they ask you to tell them how many extra judging servers they must operate.

The first line of the input contains a single integer S (2 ≤ S ≤ 100 000), which is the number of sites. The sites are numbered from 0 to S − 1.

The next S lines describe the sites. Each of these lines starts with an integer `(0 ≤ ` < S), which is the number of links that this site has to a site with a larger number. Then follow `integers in ascending order, which are the sites to which those links go. Note that, although links are two-way, they are only mentioned in the lower numbered site’s line. The total number of links is no more than 100 000.

Display the minimum number of extra judging servers the organisers must operate.