树分解（宽度 2）

（Tree Decomposition (Width 2)）

问题描述

给定一个简单无向图，含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边为 $(u_i, v_i)$。

判断该图的树宽是否 $\le 2$。
若是，构造一个宽度不超过 2 的树分解：即一棵含 $K$ 个节点的树，每个节点是一个“包”（bag）——原图顶点的子集，满足：

1. 每条边 $(u_i, v_i)$ 至少被一个包包含（即存在某个包含 $u_i$ 和 $v_i$）；
2. 对每个原图顶点 $i$，所有包含 $i$ 的包在树中构成连通子树；
3. 每个包的大小 $\le 3$（因宽度 = 最大包大小 $-1$，故宽度 $\le 2 \iff$ 包大小 $\le 3$）。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq M \leq 5 \times 10^5$
• 图是简单的（无自环、无重边）

输入

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

注：输入首行为 p tw N M，其中 p 和 tw 为固定字符串（参考 PACE 2017 Track A 格式），$N, M$ 为顶点数与边数；后续 $M$ 行为边，顶点编号为 1-indexed。

输出

• 若树宽 $\ge 3$：输出一行 -1
• 否则：输出树分解，格式如下：

  s td K w N
  b 1 v ... v
  b 2 v ... v
  ...
  b K v ... v
  a 1 b 1
  a 2 b 2
  ...
  a_{K-1} b_{K-1}
  

其中：

• s td K w N：K 是包的数量，w 是树分解的宽度（应为 0、1 或 2），N 是原图顶点数；
• b i v ... v：第 $i$ 个包包含的顶点（1-indexed，按任意顺序）；
• a i j：树中第 $i$ 条边连接包 $i$ 与包 $j$（1-indexed）；
• 每个包大小 $\le w+1 \le 3$；
• 顶点编号均为 1-indexed。

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