34079번 - 좋아하는 다이아몬드가 안경을 깜빡했다 스페셜 저지

문제

사실 오늘은 렌즈 껴봤어. 잘 보여.

— 미에 아이

오늘은 3월 14일, 파이데이다. 나는 짝사랑하고 있는 다이아몬드 양을 위해 블루베리 파이를 준비해 왔다.

다이아몬드에게 파이를 건네주기 위해 다가갔을 때, 무언가 평소와 다르다는 것을 깨달았다. 그녀가 늘 쓰고 다니던 안경이 보이지 않았던 것이다.

안경을 깜빡한 다이아몬드는 잘 안 보여서인지 미간을 찌푸려서 눈매가 사나웠다. (이건 이것대로 귀엽지만 말이다)

오랜만에 다이아몬드의 선명한 눈동자를 본 그 순간 아찔한 현실을 깨달았다.

잠깐, 내가 준비한 유일한 파이가 다이아몬드를 위한 것이라니, 이건 고백하는 거나 마찬가지잖아! 만약 거절이라도 당한다면 죽는 수밖에 없어...

아무래도 계획을 변경하는 게 좋겠다...

당신은 좋아하는 다이아몬드에게 파이를 전달하기 위해, 하굣길에서 그녀를 미리 기다리려고 한다.

이 마을에는 $N$개의 장소가 있으며, 서로 다른 두 장소를 잇는 $M$개의 양방향 도로가 있다. 모든 장소의 위치는 1ドル$부터 $N$까지의 정수로 나타낼 수 있고, 학교는 1ドル$번 장소에, 다이아몬드의 집은 $N$번 장소에 위치한다. 도로를 통해 마을의 모든 장소를 오갈 수 있으며, 하나의 도로가 잇는 두 장소를 이동하는 데 걸리는 시간은 모두 같다.

당신은 그동안 다이아몬드를 지켜보며 다음과 같은 사실을 알아냈다.

• 다이아몬드는 효율을 중요하게 여기는 성격이라서 집에 갈 때 항상 가장 빠른 길을 선택한다.
• 하지만 매일 같은 길만 걷는 건 지루해하기 때문에, 가능한 최단 경로 중 그날 기분에 따라서 하나를 선택한다.

만약 당신이 아무 장소에서나 기다렸다가는 서로를 못 보고 지나칠 수 있다. 그러니까 다이아몬드가 어떤 경로를 선택하든 그녀를 항상 만날 수 있는 장소를 고르자.

물론, 학교에서 직접 파이를 준다거나 다이아몬드의 집에서 기다리는 것은... 역시 고백이나 마찬가지이기 때문에 가능하면 피해야 한다!

그녀가 도착하면 ‘우연히’ 마주친 척하고, 준비했던 파이를 건네주자.

안경을 쓰지 않은 다이아몬드의 눈을 똑바로 쳐다볼 수 있을지는 자신이 없다.

하지만 다이아몬드에게 나의 표정이 잘 보이지 않는 지금이라면, 드러나는 속마음을 들키지 않을 수 있을지도 모른다.

저기, 아까 미처 나눠주지 못한 건데...

입력

첫 번째 줄에 장소의 수 $N$과 도로의 수 $M$이 공백으로 구분되어 주어진다. (2ドル\leq N\leq 200,000円$; $N-1\leq M\leq\min \left( \dfrac{N \times (N-1)}{2}, 300,000円 \right)$)

다음 $M$개의 줄에 걸쳐, $i$번째 도로가 잇는 두 장소의 위치를 나타내는 정수 $u_{i},ドル $v_{i}$가 공백으로 구분되어 주어진다. (1ドル\leq u_i,v_i\leq N$; $u_i\ne v_i$) 임의의 서로 다른 두 장소를 잇는 도로는 최대 1ドル$개 존재한다.

출력

학교나 다이아몬드의 집을 제외한 장소에서 다이아몬드를 항상 만날 수 있는 경우, 그 장소의 위치를 나타내는 정수 $V$ (2ドル\leq V \leq N-1$)를 출력한다. 그러한 장소가 여러 곳일 경우 그 중 아무 한 장소의 위치를 출력한다. 다이아몬드를 항상 만날 수 있는 장소를 찾을 수 없다면, 학교에서 마음을 전할 용기를 내야 한다. 따라서 1ドル$을 출력한다.

제한

노트

이 문제의 지문은 다이아몬드의 공식 설정과 다를 수 있다.