전령

비트나라에는 $1$번부터 $n$번까지 번호가 붙은 도시가 있고($3 \le n \le 500$), $1$번 도시가 수도이다. 도시들은 양방향 도로로 연결되며, 서로 다른 두 도시를 직접 잇는 도로는 많아야 하나이다. 도로망은 2-연결(2-connected)이다. 즉 서로 다른 두 도시 $A$, $B$에 대해, 처음 갈 때 지나간 중간 도시를 다시 지나지 않고도 $A$에서 $B$로 갔다가 다시 $A$로 돌아올 수 있다. 달리 말하면 어떤 두 도시 사이에도 중간 도시를 전혀 공유하지 않는 두 개의 경로가 존재한다.

왕은 다가오는 공격을 알리기 위해 두 명의 전령을 보낸다. 두 전령 모두 수도에서 출발한다. 전령은 도로를 따라 이동하며 같은 도시를 여러 번 지나도 되지만, 각 도시에 처음 도착하는 순서는 미리 정해 둔 계획을 따라야 한다.

계획이란 $x_1 = 1$인 모든 도시의 나열 $x_1, x_2, \dots, x_n$($1..n$의 순열)이다. $x_i$에서 $x_{i+1}$로 이동할 때 전령은 이미 방문한 도시만 지나갈 수 있으므로, $x_{i+1}$은 $x_1, \dots, x_i$ 중 적어도 한 도시와 도로로 직접 연결되어 있어야 한다.

적은 수도가 아닌 도시 정확히 하나를 몰래 점령해 두었다. 전령이 점령된 도시에 도착하는 순간 그곳에 경고를 전한 뒤 붙잡히며, 그 이후로는 더 이동하지 못한다. 두 계획은, 점령된 도시가 수도가 아닌 어느 도시이더라도 모든 도시가 두 전령 중 적어도 한 명에게 경고를 받도록 정해야 한다(점령된 도시는 그곳에서 붙잡히는 전령이 경고를 전한 것으로 친다).

첫째 줄에 도시의 수 $n$이 주어진다. 둘째 줄에 도로의 수 $d$가 주어진다. 이어지는 $d$개의 줄에는 각각 서로 다른 두 정수 $a$와 $b$($1 \le a, b \le n$)가 주어지며, 이는 도시 $a$와 $b$를 직접 잇는 도로를 뜻한다. 각 도로는 정확히 한 번씩만 나열된다.

두 계획을 한 줄에 하나씩 출력한다. 각 계획은 $n$개의 도시 번호를 공백 하나로 구분하여 적으며, 첫째 줄은 첫 번째 전령의 계획, 둘째 줄은 두 번째 전령의 계획이다. 두 계획 모두 수도($1$번 도시)에서 시작해야 하며, 점령될 수 있는 모든 도시에 대해 위 조건을 만족해야 한다.

조건을 만족하는 계획의 쌍은 여러 개일 수 있다. 그중 사전순으로 가장 작은 쌍을 출력한다. 즉 유효한 모든 쌍 가운데 첫째 줄(도시 번호의 나열)이 사전순으로 가장 작은 것을 고르고, 첫째 줄이 같은 쌍이 여럿이면 둘째 줄이 사전순으로 가장 작은 것을 고른다.