You are given a simple, undirected graph with $N$ vertices and $M$ edges. Its edges are $(u_i, v_i)$.
Determine whether the tree width of the graph is no more than 2. If it is, construct a tree decomposition with tree width no more than 2.
In other words, construct a tree with $K$ vertices, and the bag (subset of vertices in the original graph) $B_0, B_1, \cdots, B_{K - 1}$ on each of its vertices.
$N$ 頂点 $M$ 辺の単純な無向グラフが与えられる。辺は $(u_i, v_i)$。
木幅が $2$ 以下か判定し、$2$ 以下の場合は木幅が $2$ 以下の木分解を構成してください。
つまり、以下の条件を満たす $K$ 頂点の木と、その各頂点にバッグ(=元のグラフの頂点の部分集合) $B_0, B_1, \cdots, B_{K - 1}$ を構築してください。
Input and output are in the format used in PACE 2017 Track A. Also refer to the samples.
入出力は PACE 2017 Track A で使用されたフォーマットで与えられる。 サンプルも参考にせよ
p tw $N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
Note that $u_i, v_i$ are 1-indexed.
$u_i, v_i$ は 1-indexed なことに注意せよ
If the tree width is $3$ or larger, output $-1$ in the first line. (This is not the format used in PACE 2017 Track A)
Otherwise, output in the following format.
木幅が $3$ 以上の場合は最初の行に $-1$ を出力してください。(これは PACE 2017 Track Aのフォーマットではないです)
そうでない場合以下の形式で出力してください。
s td $K$ $w$ $N$
b $1$ $v$ $\ldots$ $v$
b $2$ $v$ $\ldots$ $v$
$\vdots$
b $K$ $v$ $\ldots$ $v$
$a_1$ $b_1$
$a_2$ $b_2$
$a_{K - 1}$ $b_{K - 1}$
p tw 5 6 1 2 2 3 3 4 4 5 2 4 4 1
s td 5 2 5 b 1 5 b 2 4 5 b 3 3 4 b 4 2 3 4 b 5 1 2 4 1 2 2 3 3 4 4 5
p tw 4 6 1 2 1 3 1 4 2 3 2 4 3 4
-1