As you have noticed, there are lovely girls in Arpa’s land. People in Arpa's land are…
- User
As you have noticed, there are lovely girls in Arpa’s land.
People in Arpa's land are numbered from 1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crushi.
Someday Arpa shouted Owf loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.
The game consists of rounds. Assume person x wants to start a round, he calls crushx and says: "Oww...wwf" (the letter w is repeated t times) and cuts off the phone immediately. If t > 1 then crushx calls crushcrushx and says: "Oww...wwf" (the letter w is repeated t - 1 times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (t = 1). This person is called the Joon-Joon of the round. There can't be two rounds at the same time.
Mehrdad has an evil plan to make the game more funny, he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round. Find such t for Mehrdad if it's possible.
Some strange fact in Arpa's land is that someone can be himself's crush (i.e. crushi = i). Input
The first line of input contains integer n (1 ≤ n ≤ 100) — the number of people in Arpa's land.
The second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush.
Output
If there is no t satisfying the condition, print -1. Otherwise print such smallest t.
Examples
Input
4 2 3 1 4
Output
3
Input
4 4 4 4 4
Output
-1
Input
4 2 1 4 3
Output
1
Note
In the first sample suppose t = 3.
If the first person starts some round:
The first person calls the second person and says "Owwwf", then the second person calls the third person and says "Owwf", then the third person calls the first person and says "Owf", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is 1.
The process is similar for the second and the third person.
If the fourth person starts some round:
The fourth person calls himself and says "Owwwf", then he calls himself again and says "Owwf", then he calls himself for another time and says "Owf", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when x is 4.
In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.
Assistant
We need to understand the problem.
We have a functional graph on n nodes: each node i has exactly one outgoing edge to crush[i]. So it's a directed graph where each node has out-degree 1. There can be self-loops, cycles, etc.
We define a game round: Starting from person x, with a parameter t (≥1). x calls crush[x] and says "Oww...wf" with t w's? Actually: "Oww...wwf" with the letter w repeated t times. And cuts the call. So effectively, the message is passed along the chain, decreasing t each step? Wait: The description: "If t > 1 then crushx calls crushcrushx and says: 'Oww...wwf' (the letter w is repeated t - 1 times) and cuts off the phone immediately. The round continues until some person receives an 'Owf' (t = 1)." So it seems that when someone calls someone else, they say the phrase with w repeated t times, where t is the remaining count? Actually the process: Person x starts the round with parameter t. They call crush[x] and say the phrase with t w's. Then if t > 1, the person they called (crush[x]) calls crush[crush[x]] and says the phrase with (t-1) w's. Continue. So the number of w's decreases by 1 each step until it becomes 1. So after exactly t steps of calling, someone receives phrase with w repeated 1 (i.e., "Owf") and that person is the Joon-Joon of the round. So starting from x with t, the sequence is: x0 = x, then x1 = crush[x0], x2 = crush[x1], ..., x_t = crush[x_{t-1}]. The Joon-Joon is x_t, because after t calls, the phrase has t w's? Wait need to careful: At step 1, x calls crush[x] with t w's. Then crush[x] (if t>1) calls crush[crush[x]] with t-1 w's. So after k calls, the current caller says phrase with (t - k + 1) w's? Let's formalize:
- Start: x_0 = starter, they will call x_1 = crush[x_0] and send a message with parameter t. So x_1 receives a call with t w's.
- Then if t > 1, x_1 (now the receiver) becomes the caller for the next step? Actually description: "If t > 1 then crushx calls crushcrushx and says: 'Oww...wwf' (the letter w is repeated t - 1 times) and cuts off the phone immediately." So after receiving call with t w's, if t > 1, they call their crush and send phrase with t-1 w's. So the pattern: For step i (starting from 0), the person who receives the call with parameter (t - i) will, if (t - i) > 1, call their crush with parameter (t - i - 1). Actually initial call from x_0 to x_1 with t w's, so x_1 receives t w's. Then x_1 (if t>1) calls x_2 with t-1 w's, so x_2 receives t-1. Then x_2 (if t-1>1) calls x_3 with t-2, etc. So after k steps of calls, the person x_k receives the call with parameter (t - k + 1)? Let's check: k=1: x_1 receives t. k=2: x_2 receives t-1. So general: x_k receives (t - (k-1))? Actually at step number k (starting from first call as step 1), the call is from x_{k-1} to x_k and the phrase has (t - (k-1)) w's? Because step1: from x0 to x1 with t, t - 0 = t. step2: from x1 to x2 with t-1, t - 1 = t-1. So step i (i from 1 to t) the call from x_{i-1} to x_i has (t - i + 1) w's. So after t calls, x_t receives call with (t - t + 1) = 1 w, i.e., "Owf". So indeed, the Joon-Joon is the person at the end of the chain of length t: after following crush edges t times from x, we get the Joon-Joon. So Joon-Joon of round started by x with parameter t is: f^t(x) where f(i) = crush[i], and f^t means applying f t times.
Thus the round: start at x, after t steps we land on y = f^t(x). y is the Joon-Joon.
Now condition: Mehrdad wants to find smallest t >= 1 such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round.
Interpretation: For all x, define y = f^t(x). Then we require that starting from y, with the same t, the Joon-Joon should be x. That is: f^t(y) = x. Because "by starting from y, x would become the Joon-Joon of the round" means if y starts a round (with same t), then the Joon-Joon is x. So condition is: For all x, f^{2t}(x) = x? Actually: y = f^t(x). Then need f^t(y) = x. So f^t(f^t(x)) = f^{2t}(x) = x. So we require that f^{2t}(x) = x for all x. But is that sufficient? Let's examine: Condition is: for each x, if y = f^t(x), then f^t(y) = x. That is exactly f^{2t}(x) = x. But also we need that for each x, it's consistent? Possibly also need that the mapping x -> y is a bijection? Actually f^t must be an involution? Because applying f^t twice gives identity. But note: For a given t, we need for each x, f^t(f^t(x)) = x. This means f^t is a permutation that is its own inverse, i.e., an involution (each element order 1 or 2). But does the problem ask something more? Let's read again: "he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round." That is exactly that f^t is an involution: f^{2t} = identity. But there may be additional constraints? Actually note that the game rounds cannot happen simultaneously, but that's not relevant.
Now we need to find smallest t >=1 satisfying that for all x, f^{2t}(x) = x. But we must also consider the condition "if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round." This only imposes condition for pairs (x, y) that actually occur as (x, f^t(x)). If for some x, f^t(x) = y, it implies that if we start from y we get x. That is exactly f^t(y) = x. So yes, f^{2t}(x) = x.
But is it necessary that f^t is a bijection? In a functional graph, f^t is not necessarily a permutation if there are nodes that are not part of cycles? However, note that for f^{2t}(x) = x to hold for all x, every node must be on a cycle of length dividing 2t? Actually f^{2t}(x)=x means that applying f 2t times returns to x. That implies that every node must be in a cycle of the functional graph (since if a node eventually goes into a cycle but is not on the cycle, then iterating many times you eventually stay in the cycle and never return to the original node unless the tail leads back? Actually for a node not on a cycle, eventually it reaches a cycle and then stays there; applying f repeatedly never returns to the original node. So f^{k}(x)=x for some k>0 is possible only if x is in a cycle. Because if x is not in a cycle, it has a path to a cycle, but once it enters the cycle it never returns to the non-cycle nodes. So for f^{2t}(x)=x to hold, every node must be on a cycle. That is, the functional graph must consist only of cycles (i.e., each node's crush leads to a cycle that includes itself? Actually if every node is in a cycle, then the graph is a disjoint union of cycles; no trees feeding into cycles). But the problem allows any crushes, so there may be nodes that are not in cycles (like nodes that eventually go to a cycle). In that case, is it possible to have t such that f^{2t}(x)=x for all x? No, because for a node x not in a cycle, f^{k}(x) will be on the cycle after some steps, and cannot equal x. So unless every node is in a cycle, it's impossible. But maybe the condition only applies when you start a round and get a Joon-Joon; but if x starts a round, it will always have some Joon-Joon y = f^t(x). The condition requires that if we start from y, we get x. But if x is not on a cycle, could that still be satisfied? Let's test: Suppose x is not on a cycle, say it points to a node y that is on a cycle. For a given t, y = f^t(x). Then starting from y, we apply f t times: f^t(y). Since y is on a cycle, f^t(y) will be some node on the cycle, not necessarily x because x is not on the cycle. So it's impossible to have f^t(y) = x. Thus indeed, for the condition to hold, all x must be such that f^t(x) is also a node from which applying f^t yields x, which implies x must be on a cycle. More precisely, if f^{2t}(x)=x, then x is periodic, so it's on a cycle. So necessary condition: every node is on a cycle, i.e., the functional graph is a disjoint union of directed cycles (each node's crush leads to a node, and since each node has exactly one outgoing edge, being on a cycle means that the graph is composed entirely of cycles). So if any node is not part of a cycle (i.e., it's in a tree leading to a cycle), then no t satisfies the condition, output -1.
Thus we first check if the graph consists only of cycles. That is, each node is in a cycle. Equivalent: for each node i, when we follow the crush edges, we eventually loop back to i. This means that the functional graph is a set of disjoint cycles. This can be checked by detecting cycles and ensuring all nodes are visited in cycles.
Now assuming the graph is composed of cycles, we need to find smallest t >=1 such that for all nodes x, f^{2t}(x)=x. Since all nodes are on cycles, f is a permutation consisting of cycles (each cycle corresponds to a directed cycle in the functional graph). So f is a permutation (bijection). Then f^t is also a permutation. Condition f^{2t} = identity permutation. That means that for each cycle, the permutation f^{2t} restricted to that cycle is identity. Since f is a cycle of length L (say), the condition that f^{2t} = identity on that cycle means that L divides 2t. Because for a cycle of length L, the permutation f acts as a cyclic shift of order L. Then f^k is identity on that cycle iff L divides k. So we need L | 2t for each cycle length L present in the graph.
Thus we need t >= 1 such that for each cycle length L_i (distinct), L_i divides 2t. Equivalent: 2t must be a common multiple of all cycle lengths L_i. Then t is (some multiple). We need the smallest t satisfying this.
But careful: Could there be additional constraints? Since condition is f^{2t}(x) = x, yes it's exactly that. However, is it also required that from x, after t steps we land on y, and from y after t steps we land on x? That's exactly f^{2t}(x)=x but also implies that f^t is an involution, meaning each cycle of f^t consists of transpositions or fixed points. But given f is a permutation composed of cycles of lengths L_i, the condition L_i | 2t ensures f^{2t}=id. That is sufficient and necessary.
But is there any nuance about "smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round." Let's test with the examples.
Example 1: n=4, crush = [2,3,1,4]. So the graph: 1->2->3->1 (cycle length 3). 4->4 (self-loop, cycle length 1). So cycles lengths: 3 and 1. We need t such that both 3 | 2t and 1 | 2t. 1 divides anything. So need 3 | 2t. Smallest t: t=3 gives 2t=6 divisible by 3. t=1.5? No integer. t=3 works. Output 3. matches.
Example 2: n=4, crush = [4,4,4,4]? Actually 4 4 4 4 means all point to 4. So graph: 1->4, 2->4, 3->4, 4->4 (self-loop). So nodes 1,2,3 are not in cycles (they go to 4, but 4 is a self-loop; they are not on cycles because from 1 we go to 4, then from 4 we stay at 4, never returns to 1). So not all nodes in cycles, so impossible -> -1. Output -1. matches.
Example 3: n=4, crush = [2,1,4,3]. Graph: 1<->2 (cycle length 2), 3<->4 (cycle length 2). All cycles. Lengths: 2,2. Need t such that 2 | 2t. That's always true for any t? Actually 2 divides 2t for any integer t, because 2t is even. So smallest t>=1 is t=1. Output 1. matches.
So our reasoning is correct.
Thus the problem reduces to:
- For each i from 1 to n, find the cycle that contains i. Since each node has out-degree 1, we can compute the length of the cycle each node is part of, but we must detect if any node is not in a cycle (i.e., in a "tail"). That can be done by visiting nodes and marking; typical method: for each node not visited, follow the path until we either encounter a node already in the current stack (cycle) or a node already processed that is known to be not part of a cycle? Actually given that each node has exactly one outgoing edge, we can detect cycles using visited states: 0 = unvisited, 1 = visiting (in current stack), 2 = processed. When we encounter a node in state 1, we've found a cycle; we can compute its length and mark those nodes as part of a cycle (store cycle length for each node in that cycle). When we finish exploring, nodes that are not in a cycle will end up in state 2 without being assigned a cycle length. Alternatively, we can compute for each node the length of its cycle if it's in one, else 0. Then check that all nodes have cycle length >0. However careful: If a node is on a cycle, it will be assigned a length; nodes that are not on a cycle are not part of any cycle, so we can detect them.
But there is also the possibility of cycles with tails: nodes that lead into a cycle but are not themselves in the cycle. For such nodes, when we traverse, we will eventually hit a cycle. Those nodes are not part of any cycle, so they fail condition.
Thus algorithm:
-
Read n, array crushes (1-indexed). Let f[i] = crush[i].
-
For each i from 1..n, if not visited, traverse from i following f, keep a list of visited nodes in current path, and a dictionary of step indices (for cycle detection). When we hit a node already visited in the current path, that forms a cycle. Compute the cycle length L as current_step - step[node] + 1. Then assign that L to all nodes in the cycle (the ones from node to end of path). Also for nodes before the cycle (the tail), they are not in a cycle, we can mark them as non-cycle (or just later detect that they didn't get a cycle length). Continue.
Implementation details: We'll have arrays: cycle_len[i] = 0 initially. visited state: 0 unvisited, 1 in current stack (visiting), 2 done (processed). Or we can do:
- For each i, while not visited[i], start a path: use a map to store step number for nodes in current traversal. Starting from i, step count = 0, cur = i, and we push nodes onto a list path. At each step, mark cur as visiting? Actually we can use an array "state" where 0=unvisited, 1=visiting, 2=done. When we start a new traversal, we follow until we either hit a node with state 2 (meaning it's already processed and we know its cycle status) or state 1 (cycle found). However we need to compute cycle lengths and assign to nodes in the cycle. The typical approach: Use DFS with state. For each node u not visited, set state[u]=1, then recursively go to v=f[u]. If v has state 1, then a cycle is found; we can compute its length by walking from v back to u along parent pointers? But since it's a functional graph, we can just traverse from v counting until we return to v. Another simpler method: Use iterative path tracking.
Simplify: Use an array "vis" initialized to 0. For each i from 1..n where vis[i]==0, we simulate following f, storing order in a vector "stack" and also a map from node to index in the stack. While vis[cur]==0, set vis[cur] = i (or set a timestamp? Actually we need to detect cycles: if we encounter a node that is currently in the stack (i.e., its vis is not yet assigned as part of a cycle, but we need to differentiate nodes that are in current traversal vs nodes already processed). One common approach: use an array "mark" initially all 0. Then for each i, if mark[i]==0, we start at i, assign a unique "run_id" or incremental step count? Actually we can do:
- For each node, we can compute its "cycle length" by using a DFS that returns the length of cycle for nodes that are in cycles, and 0 for tails. But we need to ensure we don't recompute.
Simpler: Since n <= 100, we can just brute force to detect cycles and tails. For each node i, we can simulate the functional graph for up to n steps to detect if it enters a cycle that includes i? Actually we can compute for each node the length of its cycle (if any) by finding the smallest k>0 such that f^k(i) = i. If such k exists and <= n? But cycles can be up to n, and we can compute by simulating up to n steps and checking if we ever return to i. But we also need to know if it's part of a cycle at all: A node is in a cycle iff there exists k>0 such that f^k(i) = i. For n <= 100, we can for each i simulate up to n steps and see if we come back to i. If yes, then the node is in a cycle; we can compute the length by continuing until we see i again? Actually we can find the period: we can keep a visited set for that simulation, record the step when we first see a node, if we encounter a node we've seen before, it might be i or not. But to confirm i is in a cycle, we need that after some steps we return to i. So we can just simulate from i, track visited nodes in order, until we either revisit a node; if that node is i, then i is in a cycle and the cycle length is the difference in steps; if it's not i, then i is not in a cycle because the cycle does not include i. This works since n small. For each node we can compute its cycle length if it's in a cycle; if not, mark as invalid. Then after all nodes, we check if any node has cycle length = 0 (not in a cycle). If so, output -1.
But careful: For nodes in the same cycle, each will be identified as being in a cycle and we can compute its cycle length. But the lengths computed for each node should be the same (the length of its cycle). So we can compute cycle_len[i] for each i using this simulation. But we must ensure that for nodes in a tail, we correctly identify them as not in a cycle. Using the method: from i, we traverse using f, keeping a map from node to step index (starting at 0). We go while we haven't seen the current node before in this traversal. If we encounter a node that was visited earlier, then if that node is i, then i is in a cycle. But what if the cycle is, say, 2->3->4->2, and we start from 2: we see 2 at step0, then go to 3 step1, 4 step2, then back to 2 step3? Actually we will encounter node 2 again after 3 steps. That is a revisit of node 2, which is i. So i is in cycle, length = 3? Actually length is 3? But cycle is 2->3->4->2, which is length 3? Wait: 2->3 (1), 3->4 (2), 4->2 (3). So yes length 3. Good.
Now start from 1 if 1 points to 2: 1->2->3->4->2, then we will encounter node 2 again, not 1. So i=1 not revisited; so we detect that 1 is not in cycle. So algorithm works.
Complexity O(n^2) which is fine for n=100.
After we have cycle lengths for each node that is in a cycle, we check that all nodes have cycle_len[i] > 0. If any node has 0, output -1.
Otherwise, we have a multiset of cycle lengths L_i (maybe we only need distinct lengths? Actually the condition is: 2t must be a common multiple of all L_i. That is, the least common multiple of all L_i must divide 2t. But we need the smallest t such that 2t is a multiple of each L_i. Let M = lcm of all L_i. Then we need 2t to be a multiple of M, i.e., 2t % M == 0 => t % (M / gcd(M,2))? Actually we want smallest t>=1. Let M = lcm(L_i). Then condition L_i | 2t for all i is equivalent to M | 2t. So 2t must be a multiple of M. So t must be such that 2t = k * M for some integer k>=1, i.e., t = (k * M)/2. We want smallest t positive integer. So we need to find smallest integer t such that 2t is a multiple of M. That is t = M / 2 if M is even, else t = M (since then 2t = 2M, which is multiple of M). But careful: t must be integer. So if M is even, we can set t = M/2, then 2t = M, which is multiple of M. But wait: if M is even, M/2 is integer. Then 2t = M, which is a multiple of M (actually equals M). That satisfies M | 2t. So t = M/2. However, we need to check if this t satisfies each L_i dividing 2t? Since 2t = M, and M is multiple of each L_i, yes. So t = M/2 works.
If M is odd, then M/2 is not integer, so the smallest t is t = M? Because then 2t = 2M, which is multiple of M. But could there be a smaller t such that 2t is a multiple of M when M is odd? Suppose M=9, we need 2t divisible by 9. The smallest t such that 2t ≡0 mod9 is t=9? Check t=4.5 no integer; t=9 gives 18 divisible by 9. Could t=9/ ? Actually 9 is odd, the smallest t is M because 2M is the smallest multiple of M that is even? Wait, the condition is 2t must be a multiple of M. So t must be such that 2t = kM. The smallest positive integer t corresponds to smallest positive integer k such that kM is even (since left side is even). So we need kM even. Since M odd, k must be even. So the smallest even k is 2, giving t = (2M)/2 = M. So t = M. So indeed if M is odd, t = M.
Thus t = (M % 2 == 0) ? M/2 : M.
But is that always the smallest? Let's test with multiple cycle lengths: e.g., lengths 3 and 1. LCM = 3. M=3 odd -> t=3. matches example 1. Lengths 2 and 2: LCM=2 even -> t=1. matches example 3. Lengths 6 and 4: LCM=12 even -> t=6. Check: t=6 gives 2t=12 multiple of both 6 and 4? 2*6=12 divisible by 6? 12/6=2 yes; divisible by 4? 12/4=3 yes. Is there smaller t? t=3: 2t=6 not divisible by 4. t=2:4 not divisible by6. t=4:8 not divisible by6. t=6 is smallest. Good. Lengths 6 and 9: LCM=18 (even? 18 even) actually 18 is even, so t=9. Check: t=9 => 2t=18 divisible by6 and9? 18/6=3, 18/9=2 yes. t=3? 2t=6 not divisible by9. t=6? 12 not divisible by9. t=9 is smallest. So formula works.
But wait: What about the case where cycles have lengths that are not coprime? For example, lengths 2 and 6: LCM=6 even -> t=3. Check: t=3 -> 2t=6 divisible by2 and6. t=1? 2 not divisible by6. t=2? 4 not divisible by6. So t=3 is smallest.
Now consider a single cycle of length 1: LCM=1, even? 1 odd -> t=1? According to formula: if M odd => t=M=1. But check condition: For self-loop (cycle length 1), need t such that 1 | 2t always true, so smallest t=1. Yes.
So that seems correct.
But is there any other hidden nuance? The problem statement: "find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round." We interpreted as f^{2t}(x)=x. However, let's think deeper: The condition says: for each x, if x starts some round (with parameter t) and y becomes the Joon-Joon, then by starting from y, x would become the Joon-Joon. That is: if y = f^t(x), then f^t(y) = x. But is it also necessary that for each x, y is defined? Yes, f^t(x) always yields some node. So we need f^t to be an involution (i.e., f^{2t} = identity). That's what we have.
But is there any possibility that t could be such that f^t is identity? That would also satisfy f^{2t}=identity, but that's not necessary. However the smallest t that satisfies f^{2t}=identity may be smaller than the smallest t that makes f^t identity. So our condition is correct.
Now we must be careful: The condition is "for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round." It does not explicitly require that if y = f^t(x), then f^t(y) = x for all x. It says: for each x, if x starts some round and y becomes the Joon-Joon, then by starting from y, x would become the Joon-Joon. That indeed requires that for each x, for y = f^t(x), we have f^t(y) = x. That's exactly f^{2t}(x) = x. So it's consistent.
Now what about possibility of multiple possible y? Actually for a fixed t, each x has a unique y = f^t(x). So it's well-defined.
Now, we assumed that the graph must consist entirely of cycles. But is it possible that even if some nodes are not in cycles, we might still have a t that satisfies the condition? Let's test with a simple non-cycle graph. Suppose n=2: 1->2, 2->2 (self-loop). So 1 is not in a cycle (it goes to 2, but never returns to 1). Check condition: We need t such that for all x, f^{2t}(x)=x. For x=1, f^{2t}(1) must equal 1. Let's compute: f(1)=2, f^2(1)=f(2)=2, f^3(1)=2, etc. So for any t>=1, f^{2t}(1) = 2 because after the first step we are at 2, and 2 is a self-loop, so staying at 2. So f^{2t}(1)=2, not 1. So fails. So indeed impossible.
What about a graph where a node is in a tail but eventually after t steps it comes back? For a tail of length a and cycle length L, starting from a tail node, after many steps you end up in the cycle and never return to the tail node because the tail is one-way. So can't have f^k(tail) = tail for any k>0. So impossible.
Thus condition implies all nodes are in cycles.
Now we must verify that for cycles of even length, t might be half the LCM? Our derived t = M/2 if M even, else M. But is that always the smallest integer t? Let's confirm with an example: cycles lengths 2 and 4. LCM = 4 (even) => t=2. Check: 2t=4 divisible by 2 and 4. t=1? 2 not divisible by 4. So t=2 works. Could t=2 be minimal? Yes.
But wait, consider cycles of lengths 6 and 15. LCM=30 (even) => t=15. Check: 2*15=30 divisible by both. Could there be a smaller t such that 2t is a multiple of both? Need 2t multiple of 6 and 15 => t multiple of 3? Actually condition: 6 | 2t => 2t mod6 =0 => t mod3 =0. 15 | 2t => 2t mod15=0 => Since gcd(2,15)=1, this implies 15 | t. So t must be multiple of lcm(3,15)=15. So t must be multiple of 15. So smallest t=15. So t=15 is correct. Our formula gave t=15 (since M=30 even => M/2=15). Good.
But what about cycles lengths 8 and 12: LCM=24 (even) => t=12. Check: need 2t multiple of 8 and 12. That is: 8|2t => 2t = 8k => t=4k, so t multiple of 4. 12|2t => 2t =12m => t=6m, so t multiple of 6. LCM of 4 and 6 is 12. So t min=12. Yes.
Now, what about cycles lengths that include 1? 1 divides anything, but when computing LCM, including 1 doesn't change LCM. So it's fine.
Now we need to consider that the graph is composed of cycles, but there is also possibility of cycles of different lengths that are not all covered by this condition? The condition f^{2t}=identity must hold for all nodes, meaning each cycle's length L must divide 2t. That's exactly what we said.
Thus solution steps:
- Input n, array f[1..n].
- Determine for each node whether it is in a cycle, and if so, the cycle length. Use method:
- cycle_len = array of size n+1 initialized to 0.
- For i in 1..n: if cycle_len[i] == 0: simulate from i: create an empty map/dict visited_index; current = i; step = 0; while True: if visited_index.contains(current): # we encountered a node already visited in this traversal # If that node is i? Actually we need to check if the node is the start of cycle? But visited_index contains the step when we first saw that node. # The cycle starts at that node. If that node is i, then i is in the cycle; cycle length = step - visited_index[current]. # else, i is not in cycle (tail). # So we can check if current is the node where we first saw? Actually we need to detect if i is in cycle. # Better: we store the order of visited nodes in a vector. When we encounter a node that is already in visited_index, we have found a cycle. # The nodes in the cycle are those from visited_index[current] to end of order. # For each node in that cycle, assign cycle_len[node] = length_of_cycle. # For nodes before visited_index[current] (the tail), they are not in cycle, assign cycle_len = 0 (or leave as 0). # However, we need to know for our start node i: if i is among the cycle nodes, then its cycle_len will be set; else it remains 0. # Then break. # But careful: If i is not in the cycle, we might later encounter i again? Actually the traversal will stop when we see a node already visited, which could be a node that was visited earlier but not necessarily i. For i not in cycle, we will eventually hit a node that is already in the path? Actually if we start from i and follow, we will eventually enter a cycle (since every node has out-degree 1 and finite n). When we first encounter a node that is already in the visited set, that node is the first node of the cycle we entered. Since i is not in cycle, it's not that node. So the cycle does not include i. So we can then assign cycle lengths to nodes in the cycle, but we also need to mark the tail nodes as not being in a cycle. We can do that by leaving cycle_len=0 for those nodes, which we'll later check. # So algorithm: # vector order; unordered_map<int, int> pos; (node -> index in order) # cur = i; # while true: # if pos contains cur: # // cycle detected. cycle_start_index = pos[cur]; # cycle_length = order.size() - cycle_start_index; # for j from cycle_start_index to order.size()-1: # cycle_len[ order[j] ] = cycle_length; # // for nodes before cycle_start_index, they are tails, we don't assign cycle_len (leave 0) # break; # if cur has already been processed? But we also might have encountered a node that is already known to be in a cycle from a previous traversal. To avoid redoing, we could also check if cycle_len[cur] != 0. If we encounter a node with known cycle length, then we are in a tail that leads to a known cycle. Then we can stop; all nodes in this path are tails (not in cycle) and should have cycle_len=0. So we need to handle that to avoid infinite loops and also to propagate known cycle info. # However, we can simplify: Since n is small, we can compute for each node separately using the simulation that stops when we revisit a node, but we need to differentiate cycles. But we must ensure that if we process nodes in some order, we don't incorrectly assign cycle lengths to nodes that are in a cycle but we haven't processed the full cycle yet.
- A simpler approach: Use a standard algorithm to find all cycles and mark nodes in cycles with their cycle lengths. Since n <= 100, we can just compute for each node whether it is part of a cycle by checking if there exists k>0 such that f^k(i) == i, and if so compute cycle length as the smallest such k. We can do for each i: simulate up to n steps, keeping track of visited nodes in order; if we see i again, then we found a cycle length; else we eventually hit a node we've seen before that is not i; then i is not in a cycle. But careful: If we simulate from i, we might get into a loop that doesn't contain i. To know if i is in a cycle, we need to see if i appears again. So we can simulate, marking visited nodes, and if we see i again, we record the distance and declare i in cycle with that length. If we see a node we've seen before but it's not i, then we know i is not in cycle, because we entered a cycle that doesn't contain i. Also if we reach a node that we already know is not in a cycle or is in a cycle? Actually we don't need to know others; we can just stop when we encounter any node already visited in this traversal. But to detect if i is in cycle, we need to know if that repeated node is i. This method works provided we don't stop prematurely due to encountering a node we processed earlier from another start? But if we process each i independently, we don't use global knowledge, we just simulate from scratch each time. Since n=100, doing O(n^2) operations is fine. We can for each i simulate up to n steps, storing visited nodes in a set (or array of steps). If we ever return to i, then we record the length (step count) and break. If we visit a node that we've already visited in this traversal (and it's not i?), actually if we visit a node that is already visited, that indicates a cycle, but if that node is not i, then i is not part of that cycle, because we haven't seen i again. So we can conclude i not in cycle. But we must be careful: It could be that we visited i again after many steps, but we might have visited some other node earlier that is part of a cycle not containing i? Actually if i is not in a cycle, the path from i eventually enters a cycle and then loops within that cycle. At some point we will revisit a node that is in the cycle, which we would have visited earlier when we first entered it. That node is not i (since i is not in the cycle). So we detect a repeat of a node that is not i, so we conclude i not in cycle. If i is in a cycle, then after some steps we will return to i, and before that we may have visited other nodes, but we will not encounter a repeat before returning to i because the cycle is simple and i is part of it; the first repeat will be when we return to i. So that works.
Thus we can do: for i from 1 to n: steps = dict: node -> step index. cur = i, step = 0. while True: if cur in steps: if cur == i: cycle_len[i] = step - steps[i] (but careful: when we first set steps[i], step=0. When we come back, step will be some value >0, and steps[i] is 0, so length = step). Actually we need to capture that length. else: cycle_len[i] = 0 (i not in cycle) break steps[cur] = step cur = f[cur] step += 1 if step > n? We can have at most n steps before encountering a repeat. So safe.
But wait: If i is in a cycle, we will record steps for each node. When we return to i, we will detect cur == i? Actually we will have steps[i] from step 0. Then after moving step times, cur will become i again. At that point, cur is i which is already in steps, so we detect repeat and check if cur == i. Then cycle length = step - steps[i]? steps[i]=0, so length = step. However, step is the number of moves we have made when we are about to process cur? Let's track carefully:
Initialize: cur = i, step = 0. Loop: if cur in steps: // steps contains nodes visited so far. if cur == i: // this happens only after we have made some moves and returned to i. cycle_len[i] = step - steps[i]? steps[i] is 0, step is number of moves taken to reach this cur. But note: When we are at the start, we haven't moved yet. So we have visited i at step 0. Then we move: cur = f[i]; step becomes 1; check if cur in steps? Not yet. Then we continue. After L moves (where L is cycle length), we will have cur = i again. At that point, step = L (because we made L moves). cur = i is in steps, so we detect. The length of the cycle is L. Since steps[i] = 0, step - steps[i] = L. So yes.
But careful: Could we encounter a repeat of a node that is not i before we finish the cycle? If i is in cycle, the only repeat possible is when we return to i because the cycle is simple and we start at i. However, it's possible that the cycle contains i but there is a tail before entering the cycle? But if i is in cycle, there is no tail: starting from i, following edges, we remain within the cycle, and we will eventually return to i without encountering any other repeat because all nodes in the cycle are distinct until we come back to i. So it's fine.
Thus for each i we can compute cycle_len[i] (0 if not in cycle). Then after all i, check if all cycle_len[i] > 0. If any zero, output -1.
But wait: This method might assign cycle_len to nodes that are in a cycle but not all nodes in that cycle will have the same length? For a given cycle, each node in it will be identified as being in a cycle and the computed length will be the cycle length. So for nodes in the same cycle, cycle_len[i] will be the same (the cycle length). So that's fine.
But what about nodes that are in a cycle but we start from a node that is not the first node visited? Actually for each node i in the cycle, the simulation will detect that it returns to i after L steps, so cycle_len[i] = L. So all nodes in the same cycle will have cycle_len = L. Good.
Now complexity: O(n^2) maximum, fine.
Now once we have set of cycle lengths, we need to compute M = LCM of all distinct cycle lengths? Actually if there are multiple cycles with same length, LCM of all lengths is same as LCM of distinct lengths. So we can collect set of lengths.
But careful: Could there be a scenario where some cycle length is 0? We will have filtered that out.
Now compute M = lcm of all cycle lengths. However, note that M might become large? n <= 100, cycle lengths <= n, but LCM of numbers up to 100 could be huge. For example, LCM of numbers 1..100 is enormous (> 2^?), but here maximum cycle length is 100, and the number of distinct cycles could be up to 100 with various lengths, but the LCM of numbers up to 100 is massive, exceeding 64-bit? Let's estimate: LCM of numbers 1..100 is about 6.9e41 or something, definitely beyond 64-bit. But t we need is M/2 or M. t itself could be huge, but the problem constraints are small, but we need to output t as a standard integer. However, note that n <= 100, but the LCM of numbers up to 100 could be astronomically large, but we don't need to compute the full LCM if it overflows? But we need to output t, which could be huge. But the problem expects an integer answer; but are we sure the answer fits within 64-bit? Let's think: t can be as large as LCM of numbers up to 100. LCM of 1..100 is about 69720375229712477164533808935312303556800? Actually I recall LCM(1..100) is around 10^40. That is far beyond 64-bit (2^63 ~ 9.22e18). So we need to handle large integers. However, the problem is from Codeforces (round #383?). I recall this problem (Div2 C "Arpa's loud Owf and Mehrdad's evil plan") maybe has n up to 100, and the answer can be up to something like 10^? Actually typical solutions compute LCM using big integers or Python's big ints. Since we are generating Python code, we can use Python's arbitrary precision integers. That's fine.
But wait, there is an alternative: The required t is M/2 if M even else M. Since M can be huge, Python can handle it.
However, we must be cautious: M could be as large as LCM of numbers up to 100, which is huge but still within Python's big integers (which can handle arbitrarily large integers). So we can compute LCM using math.gcd (or fractions.gcd) and lcm = lcm * (d // gcd(lcm, d)). But careful with overflow not an issue.
Now confirm with examples: fine.
Now edge cases: All nodes are self-loops (cycle length 1). Then LCM of {1} = 1, odd -> t = 1. That matches expectation because t=1 yields f^1(x) = x, so y = x, then from y, x = x, condition holds. t=1 works.
Another edge: All nodes in a single cycle of length n. Then M = n. If n even -> t = n/2? But is t = n/2 always works? Condition: need L | 2t. L=n. So 2t multiple of n. If n even, smallest t = n/2 gives 2t = n, multiple of n. So t = n/2. Check: For a cycle of length n, f^t is a shift by t. f^{2t} = shift by 2t. For t = n/2, 2t = n, shift by n is identity. So condition holds. Is there any smaller t? For t < n/2, 2t < n, not multiple of n, so f^{2t} is not identity. So t = n/2 is minimal. If n odd, t = n. Works. That matches.
Now check if there could be a case where t is not exactly M/2 but something like M/ something else? Let's derive condition precisely: For each cycle length L, we need L divides 2t. So 2t must be a common multiple of all L. The smallest such 2t is lcm(L_i). However, t is integer >=1, so we need t = lcm(L_i)/2 if lcm(L_i) is even, else t = lcm(L_i). Because we want smallest t such that 2t is a multiple of M. The smallest multiple of M that is even is: if M is even, then M itself is even, so 2t = M -> t = M/2. If M is odd, then the smallest even multiple of M is 2M, so 2t = 2M -> t = M. So that's it.
But wait: Is it possible that M is even but M/2 is not integer? No, even means divisible by 2, so M/2 integer.
Thus answer = M // 2 if M % 2 == 0 else M.
Now consider multiple cycles with different lengths. For example, cycles lengths 2 and 6: M = lcm(2,6)=6, even, t=3. Check condition: For cycle length 2, 2|2*3=6, yes. For length 6, 6|6, yes. So works.
Now check scenario: cycles lengths 3 and 6: lcm=6, even, t=3. Check: For length 3, 3|2*3=6, yes. For length 6, 6|6, yes. So t=3. Could there be smaller t? t=2: 2t=4 not divisible by 3. t=1:2 not divisible by 3 or 6. So fine.
Now check scenario: cycles lengths 4 and 6: lcm=12, even, t=6. Check: 4|12 yes, 6|12 yes. t=4? 2t=8 not divisible by 6. t=3? 6 not divisible by 4. So t=6 is minimal.
Now check scenario: cycles lengths 5 and 10: lcm=10, even, t=5. Check: 5|10, 10|10. t=5 minimal? t=2:4 no, t=5 is fine.
Now check scenario: cycles lengths 3 and 5: lcm=15 odd, t=15. Check: 2t=30 divisible by 3 and 5. Could there be a t=7.5? No integer. t=15 is correct.
Now we must also consider that t must be integer and at least 1.
Thus solution appears straightforward.
But we must be careful: The condition we derived f^{2t}(x) = x for all x is necessary and sufficient? Let's double-check with example of cycles that are not symmetric? Actually consider a graph with two cycles of lengths 2 and 4. For t=2, we have: For a node in the 2-cycle, f^2(x) =? In a 2-cycle, applying f twice yields identity. So f^2(x)=x, so y = f^2(x)=x. Then f^2(y)=x, condition holds. For node in the 4-cycle, f^2(x) is shift by 2, which is an involution: f^2(f^2(x)) = f^4(x) = x because length 4 divides 4. So condition holds. So t=2 works. But M = lcm(2,4)=4, even -> t=2. Good.
Now consider cycles of lengths 2 and 3. M=6 even -> t=3. Check: For 2-cycle: t=3, f^3 on a 2-cycle: f^3 = f^(2+1) = f, because applying 2 yields identity, so f^3 = f. So y = f(x). Then f^3(y) = f(f(x)) = f^2(x) = x. So condition holds. For 3-cycle: f^3 = identity, so y=x, then f^3(y)=x. Works. So t=3 works.
Now consider if there is any subtlety about the condition "for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round." This is symmetric: x and y are paired. For f^t to be an involution (i.e., f^{2t}=identity) is necessary and sufficient. Could there be a case where f^t is not an involution but still condition holds for all x? Suppose f^t is not involution but maybe for some x, f^t(x)=y, and f^t(y)=x, but f^{2t}(x)=x still holds because f^t(y)=x and y=f^t(x) implies f^{2t}(x)=f^t(y)=x. So indeed f^{2t}(x)=x. So condition implies f^{2t}(x)=x for all x. Conversely, if f^{2t}=identity, then for any x, let y = f^t(x). Then f^t(y)=f^t(f^t(x))=f^{2t}(x)=x. So condition holds. So equivalence stands.
Thus solution is correct.
Now implementation details in Python:
n = int(input()) crush = list(map(int, input().split())) We need 1-indexed, so let f = [0] + crush.
Now compute cycle_len for each node:
cycle_len = [0]*(n+1) for i in range(1, n+1): if cycle_len[i] != 0: # already determined continue # Simulate steps = {} # node -> step count when first visited cur = i step = 0 while True: if cur in steps: # found a repeat if cur == i: # cycle containing i cycle_len[i] = step - steps[i] # steps[i] is 0 # But also we need to set cycle_len for all nodes in this cycle? Not necessary? Actually we need to know for each node if it's in a cycle. We are iterating i from 1..n, but we might process a node i that is in a cycle but we only set cycle_len[i] for i, not for other nodes in the same cycle. However later when we encounter another node j in the same cycle, we will recompute. That's okay; but we also need to ensure that for nodes not in cycles, we don't incorrectly set them to 0? They will be 0. But we must make sure that for nodes in a cycle, when we later process them, we compute cycle_len[j] correctly. However, our current loop only computes for i. If we only set cycle_len[i] when we start from i and detect i in a cycle, but we don't set other nodes' cycle_len. Then later when we process another node j in the same cycle, we will start simulation again, and it will detect a cycle containing j and set cycle_len[j] to the cycle length. That is fine because we compute it again. But there is a performance hit but n small. However, we need to also be careful for nodes that are not in cycles: when we start from i that is not in a cycle, our simulation will detect a repeat of a node that is not i, and we will break with cycle_len[i]=0. But we won't set any other node's cycle_len. That's okay. However, we might waste time but n is 100.
But we might also want to mark nodes in cycles to avoid recomputation? Not needed.
But one nuance: In simulation for i that is not in a cycle, we might traverse many nodes and eventually enter a cycle. But we only break and set cycle_len[i]=0. But we could also mark nodes we visited as not in cycles? Actually they might be tails leading to a cycle, and we want to later, when starting from a node in that tail, we will again traverse and detect not in cycle. That's okay. However, we must be careful that our simulation might not terminate if we encounter a node that we have already processed as being in a cycle? In the while loop, we only check if cur in steps (the steps dict of this traversal). If we encounter a node that has been previously processed and known to be in a cycle, but not in steps, then we would keep looping because cur not in steps, but we will eventually revisit nodes? Actually if we encounter a node that is in a cycle but not visited in this traversal, we will add it to steps