소민과 은주는 유명한 코레오그래피 댄서이다. 그러나 둘은 아직 대회에 수상한 적이 없다. 올해 대회에 수상하기 위해 둘은 새로운 안무를 만들기 위해 서로 도와 주기로 하였다. 사실 누구도 정적인 동작들을 부드럽게 이어보지 않았는데 둘은 이것을 처음으로 시도하려 한다!
소민과 은주는 $n$개의 정적동작들로 이루어진 두개의 안무를 만들고 싶다. 그들은 어떻게 정적 동작을 이을 건지 정확하게 이해하고 있고, $2n-3$개의 안무 pairs 정도면 충분하고 생각했다. pair 내부의 $(A,B)$ 의 순서는 상관없다. 즉 $B$가 $A$뒤에 append 될 수 있다면 그 역도 성립된다.
소민과 은주는 다음과 같이 춤을 춘다. 두 사람은 같은 시간동안 춤을 춘다 즉, 각각 춤은 같은 숫자의 정적 동작으로 이루어져 있다. 각각의 안무는 처음 동작으로 끝이난 다. 자세하게 보면, 두 안무 $C_1$,$C_2$는 $l$개의 정적 동작으로 이루어져 있고 $C_1(a_0,a_1,...,a_l)$ 와 $C_2(b_0,b_1,...,b_l)$에서 $a_0=a_l$,$b_0=b_l$ 이다. 청중들을 위해 $C_1$,$C_2$는 달라야 하는데, $0\le i \le l-1$에 대하여 $(a_i,a_{i+1})$는 $0\le j \le l-1$ 에 대하여 어떠한 $(b_i,b_{i+1})$ 와도 같아선 안된다. (예를 들어, $(1,2,3,4,5,1)$은 $(3,4,5,2,1,3)$ 과 다르지 만 $(1,2,3,4,5,1)$은 $(3,4,5,1,2,3)$와 같다.) 또한 관중들이 지루 할 수 있으므로, 안무는 너무 짧아선 안되고, 적어도 $3$개의 다른 정적 동작 들로 이루어져 있어야 한다.($3\le l$)
$2n-3$개의 정렬되지 않은pairs $P$가 $n$개의 정적 동작$m_1,...,m_n$에 대하여 주어진다. pair $(m_i, m_j)$에 대하여 $i \ne j$이고, $m_i, m_j$에 대하여 순서가 없다( 어느 동작을 먼저 하든 상관없다) 두개의 다른 $C_1(a_0,a_1,...,a_l)$ 와 $C_2(b_0,b_1,...,b_l)$에 대하여 $l \ge 3$ 이고, $0 \le i \le l-1$ $a_0=a_l$ ,$b_o=b_l$와 $\{ a_i,a_{i+1}\} \in P$, $\{ b_i,b_{i+1}\} \in P$를 만족하는 안무를 출력하는 프로그램을 만들어라
먼저 두 댄서가 동작 할 수 있는 정적 동작의 개수가 단일 integer input,$n(4\le n\le 100000)$형태로 제공된다. 각각의 정적 동작은 $1$ 부터 $n$ 으로 이름이 붙여있다. 이후 $2n-3$ 줄에는 정렬되지않은 pair $P$가 주어진다. 각각은 서로다른 integers 값이고, 서로다른 $P$주어진다.
만약 두개의 안무를 만들 수 없다면, $-1$을 출력한다. 만약그렇지 않으면 다음 3줄을 출력한다. 첫번째줄은 $3\le l$ 만족하는 안무길이 $l$을 출력한다. 두번째줄은 안무가 될 $l$ 개의 interger 값을 출력한다. 마지막의 반복되는 동작은 출력하지 않아야한다. 세번째 줄은 $l$ 길이의 또다른 안무를 출력한다.
input1
4
1 2
1 3
1 4
2 3
2 4
output1
3
1 2 3
1 2 4
input2
5
1 2
1 3
1 4
1 5
2 3
2 5
3 4
output2
7
1 2
3 4
5 6
5 2
3 1
6 1
4 2
4 5
2 6
3 6
1 5