{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n\n\t\t\t\t\u003carticle class\u003d\"uoj-article top-buffer-md\"\u003e\n\t\t\t\u003ch3\u003e题目描述\u003c/h3\u003e\n\u003cp\u003e给定一张 $n$ 个点 $m$ 条边的无向图,令 $k\u003d\\lceil\\frac{m}{n-1}\\rceil$,你需要判断能否找到两个不同的点 $u,v$,满足它们之间存在 $k$ 条\u003cstrong\u003e边不相交\u003c/strong\u003e路径,如果可以找到这样的 $u,v$,你需要输出这些路径,如果存在多种构造方案,输出任意一种即可。\u003c/p\u003e\n\u003cp\u003e额外需要注意的是输入\u003cstrong\u003e可能存在重边\u003c/strong\u003e,也就是对于同一个无序对 $(u,v)$,它们之间可能存在多条边,如果它们之间存在 $s$ 条边那么你可以理解为这条边可以经过 $s$ 次。\u003c/p\u003e\n\u003cp\u003e不过我们保证输入\u003cstrong\u003e不存在自环\u003c/strong\u003e。\u003c/p\u003e\n\u003ch3\u003e输入格式\u003c/h3\u003e\n\u003cp\u003e从标准输入读入数据。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e本题包含多组输入数据。\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e输入第一行一个正整数 $T(1\\le T\\le 10^4)$ 表示数据组数。\u003c/p\u003e\n\u003cp\u003e对于每组输入数据,第一行输入两个正整数 $n,m(2\\le n\\le 10^5,1\\le m\\le 2\\times 10^5)$ 表示点数和边数,接下来 $m$ 行每行两个正整数 $u,v(1\\le u,v\\le n,u\\not\u003dv)$ 描述 $u,v$ 间存在的一条边。\u003c/p\u003e\n\u003cp\u003e保证 $\\sum n\\le 10^5$,$\\sum m\\le 2\\times 10^5$。其中 $\\sum n,\\sum m$ 分别表示同一个测试点内所有输入数据的 $n,m$ 之和。\u003c/p\u003e\n\u003ch3\u003e输出格式\u003c/h3\u003e\n\u003cp\u003e输出到标准输出。\u003c/p\u003e\n\u003cp\u003e对于每组输入数据,如果不存在这样的 $u,v$,那么输出一行一个整数 \u003ccode\u003e-1\u003c/code\u003e,否则先输出一行两个正整数 $u,v$ 表示你找到的两个点,接下来输出 $k\u003d\\lceil\\frac{m}{n-1}\\rceil$ 行,每行第一个正整数 $t$ 描述你选出来的路径长度,接下来 $t$ 个正整数 $x_1,x_2,\\dots,x_t$,表示你选择了 $x_1\\to x_2\\to\\cdots\\to x_t$ 这条路径,你需要保证 $x_1\u003du$ 且 $x_t\u003dv$。且你需要保证输出的 $k$ 条路径满足边不相交的条件。\u003c/p\u003e\n\u003ch3\u003e样例\u003c/h3\u003e\n\u003ch4\u003e输入\u003c/h4\u003e\n\u003cpre\u003e\u003ccode class\u003d\"sh_plain\"\u003e3\n3 1\n1 3\n4 7\n1 2\n2 3\n3 4\n4 1\n1 3\n2 4\n1 4\n5 5\n1 2\n2 3\n3 4\n4 5\n3 5\u003c/code\u003e\u003c/pre\u003e\n\u003ch4\u003e输出\u003c/h4\u003e\n\u003cpre\u003e\u003ccode class\u003d\"sh_plain\"\u003e1 3\n2 1 3\n1 4\n4 1 2 3 4\n2 1 4\n2 1 4\n3 5\n3 3 4 5\n2 3 5\u003c/code\u003e\u003c/pre\u003e\n\u003ch4\u003e解释\u003c/h4\u003e\n\u003cp\u003e第一组输入数据,存在 $\\lceil\\frac{m}{n-1}\\rceil\u003d\\lceil\\frac{1}{3-1}\\rceil\u003d1$ 条 $1$ 到 $3$ 的边不相交路径 $1\\to 3$。\u003c/p\u003e\n\u003cp\u003e第二组输入数据,存在 $\\lceil\\frac{m}{n-1}\\rceil\u003d\\lceil\\frac{7}{4-1}\\rceil\u003d3$ 条 $1$ 到 $4$ 的边不相交路径 $1\\to 2\\to 3\\to 4,1\\to 4,1\\to 4$,注意到 $1\\to 4$ 这条边虽然经过了两次,但是在原输入中这条边也输入了两次,所以认为它们还是不同的边。\u003c/p\u003e\n\u003cp\u003e第三组输入数据,存在 $\\lceil\\frac{m}{n-1}\\rceil\u003d\\lceil\\frac{5}{5-1}\\rceil\u003d2$ 条 $3$ 到 $5$ 的边不相交路径 $3\\to 4\\to 5,3\\to 5$。\u003c/p\u003e\n\t\t\u003c/article\u003e\n\t\t\t"}}]}