33888번 - 가오리 그래프

문제

상혁이는 도서관에서 책을 빌려 보던 중, 책 한 장에 인상적인 가오리 그림이 그려진 페이지를 발견했다! 하지만 그림 위에 누군가 해 놓은 낙서를 발견했고, 자세히 보니 단순한 낙서가 아니라 가오리 그림을 따라서 그린 그래프였다. 이 낙서에 감명을 받은 상혁이는 여기에 '가오리 그래프'라는 이름을 붙였다.

왼쪽 : 가오리 그림, 오른쪽 : 가오리 그림을 따라서 그린 그래프

가오리 그래프는 $N$개의 정점과 $N+3$개의 간선으로 이루어진 무방향 연결 그래프이며 아래와 같은 특징을 가지고 있다.

• 각 정점은 6ドル$개의 핵심 정점과 $N-6$개의 일반 정점으로 구분된다. 핵심 정점은 머리$(A),ドル 왼쪽 날개$(B),ドル 중심$(C),ドル 오른쪽 날개$(D),ドル 아래쪽 날개$(E),ドル 꼬리$(F)$이다.
• 핵심 정점 쌍 중 $(A, B),ドル $(A, C),ドル $(A, D),ドル $(B, C),ドル $(B, E),ドル $(C, D),ドル $(C, E),ドル $(D, E),ドル $(E, F)$에 대해, 다른 핵심 정점을 거치지 않는 단순 경로가 유일하게 존재한다. 나머지 핵심 정점 쌍은 그러한 경로가 존재하지 않는다.
• 일반 정점은 핵심 정점 간 경로상에 위치한 정점으로, 서로 다른 2ドル$개의 정점과 인접해 있다.

상혁이는 가오리 그래프의 각 정점에 1ドル$번부터 $N$번까지 번호를 매기고, 간선에 대한 정보를 메모했다.

시간이 흐르고, 상혁이는 우연히 자신이 작성했던 가오리 그래프에 대한 메모를 발견했다. 하지만 상혁이는 책을 반납한 뒤여서 가오리 그래프의 원래 모습을 떠올릴 수 없었다. 하지만 오른쪽 날개$(D)$의 번호는 왼쪽 날개$(B)$의 번호보다 크다는 점은 알고 있다. 상혁이를 위해 가오리 그래프의 핵심 정점이 무엇인지 알려주자.

입력

첫 번째 줄에는 정점의 수 $N$이 주어진다. $(6 \leq N \leq 50)$

다음 줄부터 $N+3$개의 줄에 걸쳐 간선에 대한 정보로, 간선이 연결하는 두 정점 $U, V$가 공백으로 구분되어 주어진다. $(1 \leq U, V \leq N;$ $U \neq V)$

입력으로 주어지는 그래프는 가오리 그래프임이 보장된다.

출력

첫 번째 줄에 머리, 왼쪽 날개, 중심, 오른쪽 날개, 아래쪽 날개, 꼬리를 의미하는 핵심 정점 $A, B, C, D, E, F$의 번호를 공백으로 구분하여 출력한다. 입력으로 주어지는 조건에 해당하는 가오리 그래프가 유일하게 존재함을 증명할 수 있다.

제한

힌트

왼쪽 : 예제 1ドル$의 가오리 그래프, 오른쪽 : 예제 2ドル$의 가오리 그래프