이상한 트리 해싱

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

루트 정점이 존재하는 트리가 있을 때, 트리의 각 정점 $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$의 정점 집합을 의미한다.