하이퍼큐브

...큐브 안은 어둡다, 큐브 안은 어둡다...

새벽 다섯 시. Daniel은 눈을 뜬다. 머리가 조금 아프다. 귀에서 울리는 소리가 아직도 들린다.

그는 자신이 놀이터, 커다란 금속 상자 안에 있다는 것을 깨닫는다.

...나는 큐브 안에 있었어, 나는 큐브 안에 있었어...

그는 3년 전 COCI 2라운드 Kocka 문제에서 겪었던 비슷한 상황을 떠올린다.

...또 큐브 안이야, 또 큐브 안이야...

하지만 이번에는 상황이 훨씬 복잡하다. Daniel은 $n$차원 하이퍼큐브 $\mathcal{Q}_n$ 안에 있다. $n$개의 간선을 가진 나무 $\mathcal{T}$의 동일한 복사본 $2^{n-1}$개가 그의 주위에 흩어져 있다. 그는 곧 하이퍼큐브의 간선을 이 나무들로 타일링하는 것이 구원의 길임을 깨닫는다.

형식적으로, 하이퍼큐브 $\mathcal{Q}_n$는 노드 $0, 1, \dots, 2^n-1$을 가진 그래프이고, 노드 $x$와 $y$는 두 수의 비트별 xor가 2의 거듭제곱일 때에만 연결된다.

나무는 다음과 같은 방식으로 하이퍼큐브 위에 놓을 수 있다.

• 나무의 각 노드는 하이퍼큐브의 어떤 노드에 대응한다.
• 이 노드들은 모두 서로 달라야 한다.
• 나무에서 두 노드 사이에 간선이 있으면, 대응하는 하이퍼큐브 노드 사이에도 간선이 있어야 한다.

하이퍼큐브의 타일링은 여러 나무를 놓아 하이퍼큐브의 각 간선이 많아야 하나의 나무에 속하도록 하는 것이다.

주어진 $n$개의 간선을 가진 나무 $\mathcal{T}$의 복사본을 가능한 한 많이 사용해 하이퍼큐브 $\mathcal{Q}_n$을 타일링하라.

첫째 줄에는 하이퍼큐브의 차원인 양의 정수 $n$이 주어진다. ($1 \le n \le 16$)

다음 $n$개의 줄에는 각각 두 정수 $x$와 $y$가 주어진다. ($0 \le x, y \le n$, $x \ne y$) 이는 나무 $\mathcal{T}$에서 노드 $x$와 $y$가 간선으로 연결되어 있음을 나타낸다.

첫째 줄에 타일링에 사용한 나무의 수를 출력한다.

다음 각 줄에는 나무 $\mathcal{T}$의 복사본 하나를 놓은 방법을 설명해야 한다.

$i$번째 줄에는 $n + 1$개의 수 $a_0^{(i)}, a_1^{(i)}, \dots, a_n^{(i)}$를 출력한다. 이 수들은 $i$번째 나무에서 나무 노드 $j$가 하이퍼큐브 노드 $a_j^{(i)}$에 대응하도록 놓였다는 뜻이다. ($j = 0, \dots, n$)

세 번째 예제에 대한 설명: