350B.md (2693B)
1 Source: https://codeforces.com/problemset/problem/350/B 2 3 B. Resort 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Valera's finally decided to go on holiday! He packed up and headed for a ski resort. 22 23 Valera's fancied a ski trip but he soon realized that he could get lost in this new place. Somebody gave him a useful hint: the resort has *n* objects (we will consider the objects indexed in some way by integers from 1 to *n*), each object is either a hotel or a mountain. 24 25 Valera has also found out that the ski resort had multiple ski tracks. Specifically, for each object *v*, the resort has at most one object *u*, such that there is a ski track built from object *u* to object *v*. We also know that no hotel has got a ski track leading from the hotel to some object. 26 27 Valera is afraid of getting lost on the resort. So he wants you to come up with a path he would walk along. The path must consist of objects *v*1, *v*2, ..., *v**k* (*k* ≥ 1) and meet the following conditions: 28 29 1. Objects with numbers *v*1, *v*2, ..., *v**k* - 1 are mountains and the object with number *v**k* is the hotel. 30 2. For any integer *i* (1 ≤ *i* < *k*), there is exactly one ski track leading from object *v**i*. This track goes to object *v**i* + 1. 31 3. The path contains as many objects as possible (*k* is maximal). 32 33 Help Valera. Find such path that meets all the criteria of our hero! 34 35 Input 36 37 The first line contains integer *n* (1 ≤ *n* ≤ 105) — the number of objects. 38 39 The second line contains *n* space-separated integers *type*1, *type*2, ..., *type**n* — the types of the objects. If *type**i* equals zero, then the *i*-th object is the mountain. If *type**i* equals one, then the *i*-th object is the hotel. It is guaranteed that at least one object is a hotel. 40 41 The third line of the input contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ *n*) — the description of the ski tracks. If number *a**i* equals zero, then there is no such object *v*, that has a ski track built from *v* to *i*. If number *a**i* doesn't equal zero, that means that there is a track built from object *a**i* to object *i*. 42 43 Output 44 45 In the first line print *k* — the maximum possible path length for Valera. In the second line print *k* integers *v*1, *v*2, ..., *v**k* — the path. If there are multiple solutions, you can print any of them. 46 47 Examples 48 49 Input 50 51 ``` 52 5 53 0 0 0 0 1 54 0 1 2 3 4 55 ``` 56 57 Output 58 59 ``` 60 5 61 1 2 3 4 5 62 ``` 63 64 Input 65 66 ``` 67 5 68 0 0 1 0 1 69 0 1 2 2 4 70 ``` 71 72 Output 73 74 ``` 75 2 76 4 5 77 ``` 78 79 Input 80 81 ``` 82 4 83 1 0 0 0 84 2 3 4 2 85 ``` 86 87 Output 88 89 ``` 90 1 91 1 92 ```