P7025 [NWRRC 2017] Grand Test

给定一张 $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$ 的路径上各点。

Time limit: 3 s, Memory limit: 512 MB.