[Python 3] Union Find, O(N) Time.
\nclass UF:\n\t\tdef __init__(self,n):\n\t\t\tself.p=list(range(n))\n\t\tdef union(self,x,y):\n\t\t\tself.p[self.find(x)]=self.find(y)\n\t\tdef find(self,x):\n\
```\nclass UF:\n\t\tdef __init__(self,n):\n\t\t\tself.p=list(range(n))\n\t\tdef union(self,x,y):\n\t\t\tself.p[self.find(x)]=self.find(y)\n\t\tdef find(self,x):\n\t\t\tif x!= self.p[x]:\n\t\t\t\tself.p[x]=self.find(self.p[x])\n\t\t\treturn self.p[x]\ndef reinitializePermutation(self, n: int) -> int:\n        d = {}\n        for i in range(n):\n            if i % 2:\n                d[i] = n // 2 + (i - 1) // 2\n            else:\n                d[i] = i // 2\n\t\t\t\t\n        uf = UF(n)\n        m = collections.defaultdict(list)\n        for x in d:\n            uf.union(x, d[x])\n        for i in range(n):\n            m[uf.find(i)].append(i)\n       \n        l = set()\n        for i in m:\n            l.add(len(m[i]))\n        \n        def gcd(a, b):\n            if (a == 0):\n                return b\n            return gcd(b % a, a)  \n        def lcm(a, b):\n            return (a * b) // gcd(a, b)\n        \n        l = list(l)\n        if len(l) == 1:\n            return l[0]\n        else:\n            cur = 1\n            for i in l:\n                cur = lcm(cur, i)\n                  \n        return cur\n```
[]