import sys sys.setrecursionlimit(10 ** 9) N = int(input()) def dfs(s,t): if N==s: return True if N