题目描述
You are asked by iPhone map service to help diagnose iPhone maps location diagrams to identify instances of MULTIPATH in a map. The following example illustrates MULTIPATH property. There are four location(Places):A, B, C and D. An arrow pointing from X to Y indicates that Location X can be reached from location Y.
In this map diagram, D can be reached from both B and C, B can be reached from A, and C also can be reached from A. An MULTIPATH from X to Y is defined as a sequence of mapes X, C1, C2, C3, ..., Cn, Y where X can be reached from C1, Ci can be reached from Ci + 1 for 1 < ≤ i < ≤ n - 1, and Cn can be reached from Y. There are two paths from D to A in the example above. The first path is D, B, A and the second path is D, C, A.
A map diagram is said to contain a multipath if there exists a pair of mapes X and Y such that there are at least two different paths from X to Y. The above map diagram is a classic example of multipath. Your task is to determine whether or not a given map diagram contains a MULTIPATH.
Input
The first line of the input gives the number of test cases, T. T test cases follow, each specifies a map diagram.
The first line of each test gives the number (Integer) of location or places in this diagram, N. The locations are numbered from 1 to N. N lines follow. The ith line starts with a non-negative integer Mi indicating the number of location that map i can be reached from. This is followed by Mi distinct positive integers each from 1 to N representing those locations. You may assume that:
If there is a path from X to Y then there is no path from Y to X.
A location will never be reached from itself.
Output
For each diagram, output one line containing "#x:y", where x is the number (starting from 1) and y is "Yes" if the map diagram contains a MULTIPATH, "No" otherwise.
Limits
1 ≤ T ≤ 50.
0 ≤ Mi ≤ 10.
dataset
1 ≤ N ≤ 1,000.
small testcase file updated
SAMPLE INPUT
3
3
1 2
1 3
0
5
2 2 3
1 4
1 5
1 5
0
3
2 2 3
1 3
0
SAMPLE OUTPUT
1:No
2:Yes
3:Yes
输入格式
见题面
输出格式
见题面
样例输入
50
24
0
0
0
0
0
1 4
2 5 23
0
2 2 12
2 17 24
0
2 21 19
2 8 10
2 15 18
0
0
0
2 16 13
2 11 6
2 3 9
0
0
2 1 14
2 22 20
24
2 8 10
1 12
0
2 22 23
0
2 5 18
0
0
0
2 24 20
2 19 16
1 14
0
0
0
2 7 21
2 2 12
2 9 1
0
2 3 4
2 13 6
0
2 15 17
0
24
1 16
1 8
1 11
1 8
0
1 11
2 6 3
0
1 5
1 5
0
1 16
1 23
1 23
0
0
2 2 4
2 20 24
2 9 10
1 15
2 13 14
2 12 1
0
1 15
25
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
1 22
0
1 22
1 22
1 22
25
1 21
1 25
1 18
1 12
1 8
1 7
1 2
1 6
1 24
1 19
0
1 10
1 15
1 23
1 9
1 4
1 5
1 17
1 1
1 3
1 20
1 16
1 11
1 22
1 14
25
1 20
0
1 11
1 3
1 19
1 9
1 12
1 1
1 24
1 14
1 7
1 5
1 2
1 13
1 21
1 22
1 18
1 10
1 17
1 25
1 4
1 15
2 6 2
1 8
1 16
25
2 13 24
1 18
2 12 9
2 21 23
0
0
0
2 25 20
0
2 2 22
0
0
1 7
0
0
1 15
0
0
2 16 3
2 11 14
2 1 8
1 17
2 10 19
1 6
1 5
25
1 9
1 1
1 9
1 9
2 16 14
1 9
2 10 12
1 9
0
1 4
1 22
1 3
2 2 20
2 7 13
2 25 18
2 19 15
1 9
1 8
2 21 11
2 23 24
1 6
1 9
1 9
1 9
1 17
24
1 13
1 20
1 18
1 6
1 9
0
1 15
1 10
1 22
1 6
2 23 3
1 17
1 2
1 4
1 1
1 5
1 19
1 7
1 8
1 24
1 16
1 12
1 21
1 14
20
10 2 9 6 11 12 17 3 16 10 13
0
0
10 2 9 6 11 12 17 3 16 10 13
10 2 9 6 11 12 17 3 16 10 13
0
10 2 9 6 11 12 17 3 16 10 13
10 2 9 6 11 12 17 3 16 10 13
0
0
0
0
0
10 2 9 6 11 12 17 3 16 10 13
10 2 9 6 11 12 17 3 16 10 13
0
0
10 2 9 6 11 12 17 3 16 10 13
10 2 9 6 11 12 17 3 16 10 13
10 2 9 6 11 12 17 3 16 10 13
50
0
2 12 41
0
0
2 10 39
2 42 22
0
0
2 4 50
0
0
0
2 28 20
2 1 27
2 3 13
2 19 26
1 24
2 21 31
0
2 8 37
0
2 23 38
0
0
2 45 36
2 30 9
2 35 15
0
2 11 33
0
2 46 17
0
2 34 2
0
0
2 49 14
2 32 18
2 44 25
2 40 43
0
2 48 6
0
2 47 29
0
0
0
0
0
0
2 7 5
50
2 9 37
0
2 49 36
2 50 46
0
2 44 4
2 40 31
2 25 16
0
0
0
2 27 43
1 32
0
2 14 24
2 21 26
2 11 6
0
2 23 15
0
0
0
0
2 10 12
0
2 35 38
0
0
2 2 19
0
2 20 3
1 39
0
0
0
2 5 1
2 34 45
2 13 32
0
0
2 33 42
2 18 29
2 28 8
0
2 30 17
2 48 47
2 22 41
0
0
0
48
0
0
1 25
1 38
0
1 12
2 15 34
2 43 31
0
1 9
1 5
0
1 38
0
1 1
1 2
0
2 36 3
1 30
1 12
1 14
2 26 21
0
1 9
0
1 14
2 19 29
0
1 30
0
1 28
1 17
1 23
1 1
2 37 11
1 25
1 5
0
1 23
1 2
2 13 4
2 32 47
1 28
2 33 39
2 16 40
2 20 6
1 17
2 10 24
50
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
0
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
1 14
50
1 37
1 27
1 34
1 47
1 31
1 33
1 49
1 40
1 3
1 13
1 30
1 41
1 36
1 48
1 35
1 45
1 23
1 14
1 44
1 46
1 20
1 9
1 7
1 16
1 17
1 11
1 32
1 4
0
1 2
1 38
1 15
1 42
1 29
1 8
1 28
1 50
1 21
1 19
1 1
1 26
1 22
1 18
1 24
1 25
1 6
1 43
1 5
1 12
1 10
50
1 37
1 34
1 49
1 29
1 11
1 21
1 30
1 50
1 40
1 45
1 1
1 42
1 23
1 4
1 14
1 8
1 32
2 46 42
1 22
1 3
1 44
1 27
1 33
1 38
1 39
1 31
1 28
1 6
1 24
1 19
1 48
1 9
1 5
1 35
1 16
1 2
1 10
1 41
1 43
1 13
1 47
0
1 26
1 12
1 36
1 17
1 20
1 7
1 25
1 15
50
2 36 28
2 43 34
0
2 10 37
2 15 45
2 1 8
2 50 21
2 9 27
1 46
2 18 39
0
2 26 24
1 30
1 22
2 44 35
0
0
1 3
1 20
0
0
0
1 25
2 4 5
0
2 6 31
1 29
1 16
0
0
2 40 41
0
0
0
1 17
1 11
2 19 7
0
1 32
2 49 14
2 13 2
0
0
1 47
2 23 48
0
0
2 42 38
1 33
0
50
1 24
1 35
2 31 45
2 30 36
1 46
2 14 16
1 18
1 46
1 46
1 44
2 1 13
2 34 28
1 8
1 46
2 4 21
1 46
2 7 50
1 46
2 2 25
1 46
2 22 32
2 11 27
2 42 37
1 46
1 20
1 46
2 40 38
1 26
1 46
2 12 19
1 29
2 17 3
2 10 6
1 39
1 46
2 23 33
1 5
1 43
1 46
1 41
1 46
1 9
1 46
1 46
2 47 48
0
1 46
1 46
1 46
1 49
50
1 20
1 27
2 39 1
1 31
1 49
1 23
1 25
1 14
1 33
1 12
1 29
1 38
1 8
1 2
1 16
1 36
1 7
1 17
1 44
1 40
1 10
1 32
1 25
1 26
0
1 22
1 50
1 30
1 37
1 35
1 15
1 34
1 43
1 6
1 41
1 13
1 4
1 45
1 19
1 5
1 21
1 28
1 42
1 47
1 24
1 48
1 9
1 18
1 11
1 46
50
10 18 32 49 24 4 45 34 43 26 37
10 46 11 30 48 36 14 16 19 13 50
10 46 11 30 48 36 14 16 19 13 50
0
10 18 32 49 24 4 45 34 43 26 37
10 1 21 17 42 5 25 7 47 10 23
10 18 32 49 24 4 45 34 43 26 37
10 1 21 17 42 5 25 7 47 10 23
10 1 21 17 42 5 25 7 47 10 23
10 18 32 49 24 4 45 34 43 26 37
10 40 39 28 33 9 6 44 12 38 8
10 1 21 17 42 5 25 7 47 10 23
10 40 39 28 33 9 6 44 12 38 8
10 40 39 28 33 9 6 44 12 38 8
10 46 11 30 48 36 14 16 19 13 50
10 40 39 28 33 9 6 44 12 38 8
10 18 32 49 24 4 45 34 43 26 37
0
10 40 39 28 33 9 6 44 12 38 8
10 46 11 30 48 36 14 16 19 13 50
10 18 32 49 24 4 45 34 43 26 37
10 46 11 30 48 36 14 16 19 13 50
10 18 32 49 24 4 45 34 43 26 37
0
10 18 32 49 24 4 45 34 43 26 37
0
10 46 11 30 48 36 14 16 19 13 50
10 1 21 17 42 5 25 7 47 10 23
10 46 11 30 48 36 14 16 19 13 50
10 40 39 28 33 9 6 44 12 38 8
10 46 11 30 48 36 14 16 19 13 50
0
10 1 21 17 42 5 25 7 47 10 23
0
10 46 11 30 48 36 14 16 19 13 50
10 40 39 28 33 9 6 44 12 38 8
0
10 1 21 17 42 5 25 7 47 10 23
10 1 21 17 42 5 25 7 47 10 23
10 1 21 17 42 5 25 7 47 10 23
10 46 11 30 48 36 14 16 19 13 50
10 18 32 49 24 4 45 34 43 26 37
0
10 1 21 17 42 5 25 7 47 10 23
0
10 40 39 28 33 9 6 44 12 38 8
10 18 32 49 24 4 45 34 43 26 37
10 40 39 28 33 9 6 44 12 38 8
0
10 40 39 28 33 9 6 44 12 38 8
5
2 3 4
1 3
0
0
1 3
5
1 4
0
0
2 5 2
1 2
5
1 2
1 5
1 5
1 2
0
5
1 3
2 3 1
0
0
1 1
5
0
0
1 1
2 3 5
1 3
44
1 27
1 43
1 20
1 44
2 25 10
1 42
3 4 44 43
0
0
1 4
2 32 39
0
0
2 17 1
0
1 8
1 44
0
0
1 27
2 35 26
2 9 27
1 2
1 22
0
0
0
1 20
0
1 12
2 18 21
2 36 1
1 9
2 17 27
1 26
2 27 28
3 30 4 15
3 35 20 30
0
0
1 20
0
1 44
0
46
1 26
1 30
1 11
1 42
2 31 18
1 26
2 41 10
1 44
1 13
1 12
2 7 43
0
0
2 3 29
0
3 22 13 45
1 29
0
4 18 40 12 13
0
0
1 39
2 5 2
1 30
2 31 5
0
0
2 39 2
0
0
0
1 10
2 41 2
0
0
1 20
1 32
2 21 32
1 44
0
0
0
0
0
0
6 40 6 3 5 18 29
42
0
2 12 25
1 42
1 21
0
1 8
0
2 7 15
0
1 11
1 12
1 25
0
1 35
0
0
3 12 24 1
0
2 7 41
4 41 40 23 16
3 33 37 14
0
2 42 18
0
1 37
0
2 1 21
0
0
1 7
1 40
3 13 25 29
0
1 7
0
3 1 28 3
0
2 12 33
0
1 25
2 29 42
0
49
0
1 19
0
1 38
1 26
1 20
1 1
3 33 18 41
0
1 38
0
2 49 48
1 38
0
0
1 13
2 7 4
1 2
1 27
3 41 19 40
1 40
1 41
2 25 27
2 15 43
0
0
0
2 9 33
0
1 27
1 49
1 44
3 2 40 24
2 25 17
0
0
3 47 1 9
0
2 13 1
0
1 40
1 9
0
1 35
0
0
3 39 41 27
2 30 38
0
42
2 9 14
0
0
1 40
1 20
1 7
2 3 39
1 27
0
1 22
0
0
2 17 8
0
1 17
1 37
0
3 42 40 25
0
0
2 2 8
1 36
3 31 21 22
3 34 27 40
0
1 8
0
3 35 41 4
4 26 40 41 25
1 35
0
0
1 32
1 42
1 37
0
0
1 40
3 41 31 12
0
0
1 17
42
2 25 8
1 15
1 15
2 26 32
1 14
1 18
0
0
3 31 29 34
0
1 15
1 26
3 31 4 32
1 37
1 32
0
1 20
1 25
1 31
3 26 30 28
1 32
0
0
1 8
0
0
2 15 33
0
1 34
1 21
0
0
1 16
1 10
0
0
0
3 27 15 28
2 33 21
1 32
1 25
3 38 13 28
48
2 15 26
0
1 24
0
0
1 18
1 11
0
0
0
1 42
1 17
2 15 26
0
1 4
1 24
2 24 44
2 39 4
0
0
0
0
1 45
0
0
0
1 20
4 30 6 35 12
2 47 33
2 29 5
1 34
2 4 5
0
1 48
1 48
4 20 33 3 48
4 31 17 36 32
2 22 17
1 24
1 26
0
0
3 26 2 35
0
0
2 10 41
1 16
0
47
0
1 38
2 21 19
0
0
1 16
1 32
1 4
2 19 45
2 7 4
0
0
0
1 12
2 44 23
0
0
0
2 30 33
0
1 31
1 18
0
0
0
0
0
1 44
1 11
0
2 13 38
1 12
1 2
0
0
0
0
0
3 32 45 29
0
3 12 37 29
0
0
0
0
1 31
1 36
50
0
0
2 22 50
1 28
1 31
2 25 47
0
0
0
1 44
4 8 41 23 6
3 50 3 41
1 9
0
0
0
0
2 2 4
0
0
0
0
0
1 31
2 3 44
1 2
0
0
2 33 47
2 28 2
0
1 40
0
0
1 19
0
0
0
1 31
0
1 28
2 23 44
0
0
1 44
0
1 44
0
0
0
42
0
0
1 4
0
1 15
0
0
0
1 2
0
0
0
0
1 16
0
0
1 33
1 25
0
1 23
0
3 11 10 23
0
1 16
1 42
1 15
3 13 11 30
0
3 2 33 35
1 9
1 23
1 7
0
1 3
0
2 40 41
0
1 24
0
0
2 15 20
0
42
0
0
0
1 13
0
2 29 5
0
1 34
0
2 22 23
0
0
0
2 18 12
1 9
1 22
2 28 39
1 5
0
1 18
0
0
1 24
0
1 13
0
0
3 29 12 15
0
0
0
2 36 12
0
1 9
0
0
1 11
0
1 33
2 9 5
0
2 24 34
48
0
2 16 26
1 21
0
1 45
0
1 17
0
2 43 32
0
0
0
0
0
0
0
2 27 10
0
1 20
2 44 14
0
1 18
0
0
0
0
1 37
0
0
0
2 18 22
0
1 24
1 44
0
1 46
0
3 25 18 8
0
0
0
2 37 40
1 6
0
2 25 46
1 18
3 29 1 22
1 3
46
1 6
2 13 38
2 37 44
1 17
0
0
0
2 10 20
0
1 37
0
1 13
0
0
1 29
0
3 30 6 7
0
0
0
1 30
1 13
0
1 9
0
0
0
0
0
0
0
0
1 25
0
0
1 38
1 38
0
5 17 45 31 34 1
2 29 2
0
2 16 25
0
1 28
0
0
43
0
1 20
1 24
0
2 6 34
0
0
0
0
0
1 40
1 34
0
1 28
2 2 43
1 40
0
0
0
0
1 4
2 43 11
1 26
1 32
1 2
0
1 25
0
0
1 9
1 1
0
2 38 28
0
0
4 22 33 12 39
0
0
0
0
0
1 16
2 41 28
48
0
2 24 19
2 40 27
0
0
2 1 15
1 34
1 21
1 26
0
1 27
1 10
1 46
1 33
2 27 7
0
0
0
3 1 27 46
2 15 26
0
0
0
0
0
0
0
0
1 34
3 47 8 48
0
1 36
0
0
2 28 11
0
2 40 29
1 15
0
0
0
2 36 41
0
0
0
0
0
0
50
1 32
1 47
0
1 31
0
0
0
0
0
3 21 46 7
2 35 44
0
0
1 35
0
2 28 44
0
0
1 35
0
0
0
0
0
0
0
2 6 47
3 44 29 14
0
1 39
1 24
2 29 3
0
1 39
0
0
0
2 48 13
0
0
0
0
2 5 29
0
5 28 26 41 39 35
0
0
2 42 32
0
0
42
0
1 7
0
0
0
2 17 25
1 20
0
2 13 14
2 15 24
0
0
0
1 11
2 17 19
0
1 24
0
0
0
0
1 37
0
0
1 22
0
0
0
0
0
1 4
1 1
0
0
2 3 33
0
0
4 13 29 12 7
1 4
0
2 19 15
3 21 11 32
40
1 40
2 15 12
0
0
0
0
3 20 25 6
0
0
0
2 16 5
1 35
2 3 17
0
2 17 26
0
0
0
1 37
0
0
2 2 24
0
1 38
0
0
0
0
0
0
2 13 12
1 36
1 35
0
0
2 14 19
0
1 9
2 25 40
0
48
0
1 7
0
1 25
0
1 44
0
0
0
0
0
0
1 27
0
1 22
0
0
0
0
0
1 1
0
0
0
0
0
1 1
1 25
0
0
0
1 48
0
1 36
0
0
1 42
1 17
0
0
0
0
1 39
0
0
0
1 22
2 38 44
41
1 35
0
0
0
1 24
1 28
0
0
0
0
0
0
1 15
0
0
0
0
0
0
0
0
0
1 3
1 29
0
0
1 32
1 12
0
1 14
0
0
1 29
0
1 12
0
0
0
0
1 23
1 19
50
0
0
0
1 21
0
1 41
0
1 47
0
0
0
1 15
0
2 17 27
1 41
1 46
0
0
0
2 36 2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 23
1 25
0
1 34
1 49
0
1 21
0
1 25
0
0
0
0
0
0
0
45
0
0
0
1 37
0
1 8
0
1 28
0
0
1 27
0
0
0
0
1 36
1 39
0
1 25
1 45
0
1 38
0
0
0
1 45
0
0
1 18
0
0
0
0
0
0
2 2 27
0
0
0
1 26
0
1 18
0
0
0
50
0
1 20
0
0
0
0
0
2 4 26
0
0
0
0
1 34
0
0
0
0
1 32
0
0
0
0
1 36
0
1 34
0
0
1 16
1 26
0
2 4 15
0
0
3 19 30 40
0
0
0
0
0
0
0
0
0
1 14
0
0
1 24
0
0
0
49
1 31
1 44
0
0
0
0
0
0
1 35
1 17
1 27
0
0
0
0
1 7
0
1 4
0
0
0
2 5 6
1 8
0
0
0
0
0
0
2 31 9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 25
1 37
1 8
1 23
0
49
0
0
0
0
0
0
0
1 26
1 22
0
0
2 36 21
1 26
0
0
0
0
0
1 30
0
0
0
0
0
1 47
0
0
0
0
0
0
0
0
0
0
0
0
1 30
0
4 31 49 9 1
1 1
0
0
1 34
0
1 47
1 49
0
0
样例输出
#1:No
#2:Yes
#3:Yes
#4:No
#5:No
#6:Yes
#7:No
#8:Yes
#9:Yes
#10:No
#11:No
#12:Yes
#13:Yes
#14:No
#15:No
#16:Yes
#17:No
#18:Yes
#19:Yes
#20:Yes
#21:No
#22:Yes
#23:No
#24:Yes
#25:Yes
#26:Yes
#27:Yes
#28:Yes
#29:Yes
#30:No
#31:Yes
#32:Yes
#33:Yes
#34:Yes
#35:No
#36:No
#37:Yes
#38:Yes
#39:Yes
#40:No
#41:Yes
#42:Yes
#43:No
#44:No
#45:No
#46:No
#47:No
#48:No
#49:No
#50:No