QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[+8]

# 8757. 图

Statistics

题目描述

给定一张 n 个点 m 条边的无向图,令 k=mn1,你需要判断能否找到两个不同的点 u,v,满足它们之间存在 k边不相交路径,如果可以找到这样的 u,v,你需要输出这些路径,如果存在多种构造方案,输出任意一种即可。

额外需要注意的是输入可能存在重边,也就是对于同一个无序对 (u,v),它们之间可能存在多条边,如果它们之间存在 s 条边那么你可以理解为这条边可以经过 s 次。

不过我们保证输入不存在自环

输入格式

从标准输入读入数据。

本题包含多组输入数据。

输入第一行一个正整数 T(1T104) 表示数据组数。

对于每组输入数据,第一行输入两个正整数 n,m(2n105,1m2×105) 表示点数和边数,接下来 m 行每行两个正整数 u,v(1u,vn,uv) 描述 u,v​ 间存在的一条边。

保证 n105m2×105。其中 n,m 分别表示同一个测试点内所有输入数据的 n,m 之和。

输出格式

输出到标准输出。

对于每组输入数据,如果不存在这样的 u,v,那么输出一行一个整数 -1,否则先输出一行两个正整数 u,v 表示你找到的两个点,接下来输出 k=mn1 行,每行第一个正整数 t 描述你选出来的路径长度,接下来 t 个正整数 x1,x2,,xt,表示你选择了 x1x2xt 这条路径,你需要保证 x1=uxt=v。且你需要保证输出的 k 条路径满足边不相交的条件。

样例

输入

3
3 1
1 3
4 7
1 2
2 3
3 4
4 1
1 3
2 4
1 4
5 5
1 2
2 3
3 4
4 5
3 5

输出

1 3
2 1 3
1 4
4 1 2 3 4
2 1 4
2 1 4
3 5
3 3 4 5
2 3 5

解释

第一组输入数据,存在 mn1=131=113 的边不相交路径 13

第二组输入数据,存在 mn1=741=314 的边不相交路径 1234,14,14,注意到 14 这条边虽然经过了两次,但是在原输入中这条边也输入了两次,所以认为它们还是不同的边。

第三组输入数据,存在 mn1=551=235 的边不相交路径 345,35