트리 분해 (폭 2)

$N$개의 정점과 $M$개의 간선을 가진 단순 무방향 그래프가 주어진다. 간선들은 $(u_i, v_i)$이다.

그래프의 트리폭이 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$을 포함하는 트리의 모든 정점은 연결되어 있다.

제약 조건

• $1 \leq N \leq 500000$
• $0 \leq M \leq 500000$
• 그래프는 단순 그래프이다.

입력과 출력은 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-인덱스임에 유의한다.

트리폭이 $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-인덱스임에 유의한다.
• $w$은 2 이하의 정수이다. 이는 트리 분해의 크기이다. 항상 $2$을 출력해도 되지만, 적절한 경우 $0, 1$을 출력해도 된다. (예를 들어, 더 강력한 라이브러리를 테스트하는 경우)
• $1 + i$번째 줄에는 가방의 정보가 들어 있다. $v$은 원래 그래프에서 1-인덱스인 정점 ID이다. 각 줄에는 최대 $w + 1$개의 정점 $v$이 들어 있다.