# cycles 
# Fig. 47.3 
# input: 10

import random

n = int(input("n=? "))
ps = list(range(1,n+1))  # [1..n]
random.shuffle(ps)

print("Rearrangements:")
for i in range(n):
  print(f"{(i+1):2d} --> {ps[i]:2d}")
print()

print("Cycles:")
for i in range(n):
  first = i
  if ps[i] > 0:  # start a cycle
    print("(", end =' ')
    while True:
      r = first
      print(r+1, end = ' ')
      first = ps[first]-1
      ps[r] = -ps[r]
      if first == i:
        break
    print(")") # end cycle