题目描述

Jeremy, Richard and James like to test cars. It is always hard for them to decide where they should do it. Usually car test looks like this. They choose a country and examine its cities and two-way roads that connect them. To perform a test, they need to choose two different cities $S$ and $F$ , such that there exist three routes between them. Moreover, each city except $S$ and $F$ should be visited by at most one route, and none of the roads may be used twice.

Then each of them takes a car in city $S$ , drives along one of those routes and tries to get to city $F$ faster than others.

You are given a description of multiple countries. For each country you should decide if it is possible to choose two cities and three routes between them in a way described above.

输入格式

The first line of the input contains a single integer $T$ -- number of countries $(1 \le T \le 100 000)$ . It is followed by $T$ country descriptions.

The first line of each country description contains two integers $n$ and $m$ -- the number of its cities and roads $(1 \le n , m \le 100 000)$ . The following $m$ lines contain two integer numbers each: $u_{i}$ and $v_{i}$ -- the cities at the ends of the road $(1 \le u_{i} < v_{i} \le n)$ . All roads are two-way. Each pair of cities is connected by at most one road.

Both the total number of cities and roads in all countries does not exceed $100 000$ .

输出格式

Output the answer for each country in the order they are given in the input.

If it is not possible to test cars in this country, the answer is $−1$ . Otherwise the first line of the answer should contain two integers $S$ and $F$ -- start and finish cities. The next three lines should contain three distinct routes. Each route is described by an integer $k$ -- the number of cities it visits, and $k$ numbers $v_{1}, v_{2}, \cdots , v_{k}$ -- the cities, where $v_{1} = S , v_{k} = F$ , and there is a road between cities $v_{i}$ and $v_{i+1}$ for all $1 \le i \le k − 1$ .

题目大意

题目描述
给定一张 $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

提示

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