树分解（宽度 2）

【题目描述】

给定一张 $N$ 个顶点、$M$ 条边的简单无向图，其边为 $(u_i, v_i)$。

判断这张图的树宽（tree width）是否不超过 $2$。如果是，请构造一个树宽不超过 $2$ 的树分解。

也就是说，请构造一棵有 $K$ 个顶点的树，以及树上每个顶点对应的包（原图顶点的一个子集）$B_0, B_1, \cdots, B_{K - 1}$。

• $0 \leq K \leq 10N + M + 10$
• 对每条边 $(u_i, v_i)$，存在一个同时包含 $u_i$ 和 $v_i$ 的包。
• 对原图中的每个顶点 $i$，树中所有包含顶点 $i$ 的包所对应的顶点是连通的。

【输入】

输入与输出采用 PACE 2017 Track A 所使用的格式，另请参考样例。

p tw $N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

注意 $u_i, v_i$ 是 1-indexed 的。

【输出】

如果树宽为 $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}$

• $K$ 是树中顶点的个数。
• $a_i$, $b_i$ 是树上的边。注意它们是 1-indexed 的。
• $w$ 是不超过 $2$ 的整数，表示树分解的大小。总是输出 $2$ 是可以的，但在合适时输出 $0, 1$ 也可以。（例如用于测试更强的库）
• 第 $1 + i$ 行包含第 $i$ 个包的信息。$v$ 是原图中 1-indexed 的顶点编号。每行至多包含 $w + 1$ 个顶点 $v$。

【输入样例】

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

【输入样例2】

p tw 4 6
1 2
1 3
1 4
2 3
2 4
3 4

【输出样例2】

-1

【数据范围】

• $1 \leq N \leq 500000$
• $0 \leq M \leq 500000$
• 图是简单图。

【来源】

Library Checker（yosupo06） tree_decomposition_width_2

本题为 special judge（输出任意合法解），暂不可本地评测。