31928번 - 이상한 트리 해싱 스페셜 저지

문제

트리를 해싱한다면 두 트리가 동형인지 빠르게 확인할 수 있지 않을까?

루트 정점이 존재하는 트리가 있을 때, 트리의 각 정점 $K$의 해시값 $H(K)$는 $K$의 자식 정점 $P_1, P_2, \ldots , P_r$의 해시값 $H(P_1), H(P_2), \ldots , H(P_r)$을 사용하여 다음과 같이 계산된다.

• $H(K) = 2 ^ {H(P_1)H(P_2) \dots H(P_r)}$

이때, 리프 정점의 해시값은 2ドル$이다.

양의 정수 $h$가 주어질 때, 루트 정점의 해시값이 $h$이고 서로 동형이 아닌 두 트리 $T_1, T_2$를 출력하라.

입력

첫 번째 줄에 루트 정점이 가져야 할 해시값 $h$가 주어진다. (1ドル \le h \le 10^{18}$)

출력

첫 번째 줄에 $T_1$과 $T_2$의 크기 $n, m$을 공백으로 분리하여 출력한다. (1ドル \le n, m \le 100,000円 $)

두 번째 줄에 $T_1$의 2ドル$번 정점부터 $n$번 정점까지 각 정점의 부모 정점의 번호 $p_2, p_3, \ldots , p_n$을 공백으로 분리하여 출력한다. (1ドル \le p_i < i$)

세 번째 줄에 $T_2$의 2ドル$번 정점부터 $m$번 정점까지 각 정점의 부모 정점의 번호 $q_2, q_3, \ldots , q_m$을 공백으로 분리하여 출력한다. (1ドル \le q_i < i$)

1ドル$번 정점은 루트 정점이다.

서로 동형이 아닌 트리가 여러 쌍 있다면, 그 중 하나를 출력한다.

만약 조건을 만족하는 두 트리가 존재하지 않는다면 첫 번째 줄에 $-1$을 출력한다.

제한

노트

두 루트 있는 트리 $G, H$가 동형이라는 것은 $G$의 임의의 두 정점 $u, v$가 주어졌을 때 $G$에서 $u$가 $v$의 부모인 것과 $H$에서 $f(u)$가 $f(v)$의 부모인 것이 필요충분조건인 일대일 함수 $f:V(G) \rightarrow V(H)$가 존재한다는 것이다. 여기에서 $V(G)$와 $V(H)$는 각각 $G$와 $H$의 정점 집합을 의미한다.