8223: [yosupo] Graph - Tree Decomposition (Width 2)
[Creator : ]
Description
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.
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.
-
$0 \leq K \leq 10N + M + 10$
-
For each edge $(u_i, v_i)$, there is a bag that contains both $u_i, v_i$.
-
For each vertex $i$ in the original graph, all vertices in the tree whose bag contains vertex $i$ are connected.
Input
Input and output are in the format used inPACE 2017 Track A.Also refer to the samples.
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.
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.
Output
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.
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}$
Otherwise, output in the following format.
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$ is the number of vertices in the tree.
-
$a_i$, $b_i$ are edges in the tree. Note that they are1-indexed.
-
$w$ is an integer no more than 2. It is the size of the tree decomposition. It is acceptable to always output $2$ for it, but it is also fine to output $0, 1$ when appropriate. (For example, for testing a stronger library)
- The $1 + i$-th line contains the information of a bag. $v$ is a 1-indexed vertex ID in the original graph. Each line contains at most $w + 1$ vertices $v$.
Constraints
$1 \leq N \leq 500,000$
$0 \leq M \leq 500,000$
The graph is simple.
$0 \leq M \leq 500,000$
The graph is simple.
Sample 1 Input
p tw 5 6
1 2
2 3
3 4
4 5
2 4
4 1
Sample 1 Output
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
Sample 2 Input
p tw 4 6
1 2
1 3
1 4
2 3
2 4
3 4
Sample 2 Output
-1