D. Regina's Task
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Andrew does not want Regina to drive on the tennis courts because of memories of his failing career as a tennis player.
— Regina, GPL 2025

Regina was driving Andrew to his dreaded tennis practice when he proposed to her a very interesting question. Andrew gave Regina a simple graph of $$$N$$$ ($$$1 \leq N \leq 2\cdot 10^5$$$) nodes and $$$M$$$ ($$$0 \leq M \leq 3\cdot 10^5$$$) edges, and he requested Regina to find $$$4$$$ distinct nodes $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ such that $$$(a, b)$$$, $$$(b, c)$$$, and $$$(c, d)$$$ are all edges in the graph. Help her find nodes that satisfy these conditions, or output -$$$1$$$ if no such nodes exist.

Input

The first line contains two integers: $$$N$$$ and $$$M$$$.

The following $$$M$$$ lines contain two integers: $$$u$$$ and $$$v$$$, denoting an edge between $$$u$$$ and $$$v$$$.

It is guaranteed that $$$1\leq N\leq2 \cdot 10^5$$$ and $$$0\leq M \leq 3 \cdot 10^5$$$.

There are no self-loops or duplicate edges in the graph.

Output

If it is impossible to find four nodes that satisfy the conditions, output $$$-1$$$.

Otherwise, on $$$4$$$ separate lines, output the four nodes $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ with $$$ab$$$, $$$bc$$$, and $$$cd$$$ adjacent.

Examples
Input
4 1
3 4
Output
-1
Input
6 7
1 3
1 5
2 3
2 5
2 6
4 5
4 6
Output
5
1
3
2