Jeremy、Richard 和 James 喜欢测试汽车。对他们来说，决定测试地点总是很困难。通常，汽车测试的过程如下：他们选择一个国家，并考察其中的城市以及连接这些城市的双向道路。为了进行测试，他们需要选择两个不同的城市 $S$ 和 $F$，使得它们之间存在三条路径。此外，除了 $S$ 和 $F$ 之外，每个城市最多只能被其中一条路径经过，且任何道路都不能被使用超过一次。

然后，他们每个人在城市 $S$ 驾驶一辆汽车，沿着这三条路径中的一条行驶，并尝试比其他人更快地到达城市 $F$。

给定多个国家的描述，对于每个国家，你需要判断是否能按照上述方式选择两个城市以及它们之间的三条路径。

输入格式

输入的第一行包含一个整数 $T$ —— 国家数量 ($1 \le T \le 100\,000$)。随后是 $T$ 个国家的描述。

每个国家描述的第一行包含两个整数 $n$ 和 $m$ —— 城市数量和道路数量 ($1 \le n, m \le 100\,000$)。接下来的 $m$ 行每行包含两个整数 $u_i$ 和 $v_i$ —— 道路两端的城市 ($1 \le u_i < v_i \le n$)。所有道路均为双向。每对城市之间最多只有一条道路。

所有国家中城市总数和道路总数均不超过 $100\,000$。

输出格式

按输入顺序输出每个国家的答案。

如果无法在该国进行汽车测试，输出 $-1$。否则，输出的第一行应包含两个整数 $S$ 和 $F$ —— 起点城市和终点城市。接下来的三行应包含三条不同的路径。每条路径由一个整数 $k$ 描述 —— 该路径经过的城市数量，以及 $k$ 个整数 $v_1, v_2, \dots, v_k$ —— 路径上的城市序列，其中 $v_1 = S$，$v_k = F$，且对于所有 $1 \le i \le k - 1$，城市 $v_i$ 和 $v_{i+1}$ 之间存在一条道路。

样例

输入 1

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

输出 1

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