There are two schools $$$\text{G}$$$ and $$$\text{H}$$$ with $$$N$$$ and $$$M$$$ buildings respectively. For a pair of buildings inside the same school, there might be a undirected road between them. Every two buildings in a school are reachable via roads. The $$$i$$$-th building in $$$\text{G}$$$ has a number $$$g_i$$$ describing its type. Similarly, the $$$i$$$-th building in $$$\text{H}$$$ has a number $$$h_i$$$.

Define a "$$$\text{G}$$$-tour" to be a sequence $$$(t_1, t_2, \dots, t_k)$$$ such that for each $$$1 \le i \le k - 1$$$, the buildings $$$t_i$$$ and $$$t_{i+1}$$$ have a road between them. (In other words, it is a walk on the graph $$$\text{G}$$$.) The "characteristic" of a $$$\text{G}$$$-tour is the list of numbers on the buildings, which is $$$(g_{t_1}, g_{t_2}, \dots, g_{t_k})$$$. Define an "$$$\text{H}$$$-tour" similarly.

Suppose $$$L$$$ is an integer such that there exist a $$$\text{G}$$$-tour $$$(a_1, a_2, \dots, a_L)$$$ and an $$$\text{H}$$$-tour $$$(b_1, b_2, \dots, b_L)$$$ satisfying:

• They are both of length $$$L$$$.
• Their characteristics are the same.
• For each $$$1 \le i \le L - 2$$$, $$$a_i = a_{i+2}$$$ and $$$b_i = b_{i+2}$$$ cannot both be true.

Output the maximum possible $$$L$$$, or INF if $$$L$$$ can be arbitrarily large.

• Subtask 1 (12 points): For all $$$1 \le i \le N$$$, $$$g_i = 1$$$; for all $$$1 \le j \le M$$$, $$$h_j = 1$$$; both graphs are chains.
• Subtask 2 (20 points): For all $$$1 \le i \le N$$$, $$$g_i = 1$$$; for all $$$1 \le j \le M$$$, $$$h_j = 1$$$.
• Subtask 3 (26 points): $$$1 \le N, M \le 60$$$; for all $$$1 \le i \le N$$$, $$$g_i \le 60$$$; for all $$$1 \le j \le M$$$, $$$h_j \le 60$$$.
• Subtask 4 (42 points): No additional constraints.