题目描述

给定一张 $n$ 个节点 $m$ 条边的无向图，请在图中找出两个点 $S$ 和 $F$，使得这两点间至少存在三条不相交的路径。

输入格式

输入的第一行包数据组数 $T(1 \leq T \leq 100000)$。对于每组数据，第一行为两个整数 $n$ 和 $m$。接下来 $m$ 行每行包含两个整数 $u$ 和 $v(1 \leq u < v \leq n)$，表示节点 $u$ 和 $v$ 之间有一条边。每对节点至多被一条边连接。保证 $\sum n$ 及 $\sum m$ 不超过 $100000$。

输出格式

对于每组数据，若不存在，则输出-1。若存在，则第一行输出 $S$ 和 $F$。接下来三行输出三条路径。每行先输出路径路径包含的点数，然后依次输出由 $S$ 到 $F$ 的路径上各点。

2
6 6
3 6
3 4
1 4
1 2
1 3
2 3
3 1
1 2

1 3
3 1 2 3
2 1 3
3 1 4 3
-1