트리 뒤집기

노드에 $1 \dots N$ 번호가 매겨진 트리가 주어진다. 노드 $1$ 이 루트이며, 각 노드마다 자식 노드들의 목록이 왼쪽에서 오른쪽 순서로 주어진다.

이 트리의 잎 $K$ 를 들어 올려 새로운 루트로 만들되, 모든 간선은 그대로 두고 특히 각 노드 주위에서 간선들의 상대적인 회전 순서를 바꾸지 않는다. 이렇게 얻어지는 트리를 출력하여라.

예를 들어 아래 그림 왼쪽의 트리에서 잎 $3$ 을 새 루트로 만들면 가운데 트리를 얻는다. 오른쪽 트리는 틀린 답이다. 노드 $1$ 의 이웃을 반시계 방향으로 읽으면 원래 트리에서는 $2, 3, 4$ 이지만 오른쪽 트리에서는 $2, 4, 3$ 이기 때문이다.

    1      3       3
   /|\     |       |
  2 3 4    1       1
          / \     / \
         4   2   2   4

여기서 트리 란 연결된 비순환 그래프를 뜻하며 노드 $1$ 이 그 루트이다. 트리 (자료 구조) 를 참고하여라.

첫째 줄에 두 정수, 노드의 수 $N$ ($1 \le N \le 10\,000$) 과 새 루트가 될 잎의 번호 $K$ ($1 \le K \le N$) 가 주어진다.

이어지는 $N$ 개의 줄은 원래 트리의 각 노드를 설명한다. $(i+1)$ 번째 줄은 먼저 노드 $i$ 의 자식 수 $m_i$ 를, 이어서 그 $m_i$ 개의 자식 번호를 왼쪽에서 오른쪽 순서로 담는다.

새 트리를 설명하는 정확히 $N$ 개의 줄을 입력과 같은 노드별 형식으로 출력한다. $i$ 번째 줄은 먼저 새 트리에서 노드 $i$ 의 자식 수를, 이어서 그 자식들을 왼쪽에서 오른쪽 순서로 담는다.

잎 $3$ (자식이 $2, 3, 4$ 인 노드 $1$ 로 이루어진 성형 트리의 잎) 을 새 루트로 만드는 첫 번째 예시를 살펴보자.

1. 노드 $1$ 은 이제 자식이 $2$ 개이며, 순서대로 노드 $4$ 와 $2$ 이다.
2. 노드 $2$ 는 자식이 없다.
3. 노드 $3$ 은 자식이 $1$ 개이며, 노드 $1$ 이다.
4. 노드 $4$ 는 자식이 없다.