7191번 - Turning a Tree 다국어

문제

You are given a tree with nodes numbered 1ドル\dots N,ドル where node 1ドル$ is the root of the tree and for each node the list of its child nodes is known.¹

Find the tree we would get by lifting the leaf $K$ of the original tree to be the new root, but leaving all edges intact, including the relative ordering of the edges at each node.

For example, starting from the tree shown on the left in the figure below and making the leaf 3ドル$ the new root, we would get the tree shown in the middle in the figure. The three shown on the right in the figure would not be correct answer, because the neighbors for the node 1ドル$ (listed counter-clockwise) are 2ドル,ドル 3ドル,ドル 4ドル$ in the original tree, but 2ドル,ドル 4ドル,ドル 3ドル$ in this tree.

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

¹See also https://en.wikipedia.org/wiki/Tree_(data_structure)

입력

The first line of input contains the number of nodes $N$ (1ドル ≤ N ≤ 10,000円$) and the index $K$ of the leaf to become the new root (1ドル ≤ K ≤ N$). The following $N$ lines describe the structure of the original tree. The $(i+ 1)$-th line first contains $m_i,ドル the number of child nodes of the node $i,ドル and then the indices of the $m_i$ child nodes, listed from left to right.

출력

The output should contain exactly $N$ lines: the structure of the new tree, in the format used in the input file.

제한

노트

Explanation of the output lines:

1. Node 1ドル$ has 2ドル$ children, nodes 4ドル$ and 2ドル$ (in this order).
2. Node 2ドル$ has no children.
3. Node 3ドル$ has 1ドル$ child, node 1ドル$.
4. Node 4ドル$ has no children.