P8679 - Serval and Essay

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：2 通过：2

Serval is a new student in Japari Kindergarten.

There is an English course in the kindergarten. The teacher sets some writing tasks for students to improve their writing skills. Therefore, Serval has to complete an essay, in English.

You might know that in an essay, the author has to convince readers of several arguments by showing them evidence.

Serval have collected

n

available arguments numbered from

1

n

that can be written in his essay. For the

i

-th argument, Serval can conclude that

i

-th argument is true when the arguments numbered

ai,1,ai,2,…,ai,kia_{i,1}, a_{i,2}, \dots, a_{i,k_i}

are all true. Specially, the

i

-th argument cannot be proven true by making conclusion when

k_i = 0

. It is guaranteed that

ai,j≠ia_{i,j}\neq i

for all

i

(

1≤i≤n1\leq i\leq n

), and

ai,j≠ai,ka_{i,j}\neq a_{i,k}

when

j≠kj\neq k

.

At the beginning of his essay, Serval will set exactly one argument from all the arguments as the argument basis, which is regarded as true. Starting with the argument basis, Serval will claim that some other arguments are true by making conclusions to complete his essay. It can be shown that for the

i

-th argument with

k_i = 0

, it can be true if and only if it is the argument basis.

Serval wants to maximize the number of true arguments in the essay, so he needs to set the argument basis optimally. However, as a kindergarten student, he cannot even find out the number of true arguments he can obtain.

Could you help him find out the answer?

Each test contains multiple test cases.
The first line contains an integer  $T$  ( $1≤T≤1051\leq T\leq 10^5$ ) — the number of test cases.
For each test case:
The first line contains a single integer  $n$  ( $1≤n≤2×1051\leq n\leq 2\times 10^5$ ) — the number of the available arguments.
For the  $i$ -th line in the following  $n$  lines, there is an integer  $k_i$  ( $0≤ki<n0\le k_{i} < n$ ) followed by  $k_i$  integers  $ai,1,ai,2,…,ai,kia_{i,1},a_{i,2},\dots,a_{i,k_i}$  ( $1≤ai,j≤n,ai,j≠i1\le a_{i,j}\le n,a_{i,j}\neq i$ ) — the arguments required to make the conclusion for the  $i$ -th argument. It is guaranteed that  $ai,j≠ia_{i,j}\neq i$  for all  $i$  ( $1≤i≤n1\leq i\leq n$ ), and  $ai,j≠ai,ka_{i,j}\neq a_{i,k}$  when  $j≠kj\neq k$ .
It is guaranteed that the sum of  $n$  in all the test cases does not exceed  $2×1052\times 10^5$  and the sum of  $k_i$  in all the test cases does not exceed  $5×1055\times 10^5$ .

For the

i

-th test case, print a line containing " $\texttt{Case #i: x}$ " (without quotes), where

i

is the number of the test case starting from

1

and

x

is the answer to the test case, which is the maximum number of true arguments when setting the argument basis optimally.

Case #1: 4
Case #2: 3
Case #3: 4

For the first sample, Serval can set the  $1$ -st argument as the argument basis to obtain  $4$  true arguments in the essay. The following process shows how Serval makes conclusions in his essay.

	



	 $⋅\cdot$  Set the  $1$ -st argument as the argument basis, which is regarded as true.

 $⋅\cdot$  Conclude that  $2$ -nd argument is true because  $1$ -st argument is true.  $⋅\cdot$  Conclude that  $3$ -rd argument is true because both  $1$ -st and  $2$ -nd arguments are true.  $⋅\cdot$  Conclude that  $4$ -th argument is true because both  $2$ -nd and  $3$ -rd arguments are true.

2022 牛客1

8679: Serval and Essay

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签