Farmer John의 농장은 1…N으로 번호가 매겨진 N 개의 필드(1≤N≤10⁵)로 구성됩니다. 이들 필드 사이에는 M개의 양방향 도로(0≤M≤10⁵)가 있으며 각 도로는 두 필드를 연결합니다.

농장에는 두 개의 외양간이 있는데, 하나는 필드 1에, 다른 하나는 필드 N에 있습니다. 농부 John은 일련의 도로를 따라 두 개의 외양간 사이를 걸을 수 있는 길이 있는지 확인하고 싶었습니다. 그는 그것을 실현하기 위해 기껏해야 두 개의 새로운 도로를 건설할 용의가 있습니다. 필드의 위치로 인해 필드 i와 j 사이에 새로운 도로를 건설하는 비용은 (i-j)2입니다.

Farmer John이 불펜 1과 N이 서로 닿는 데 필요한 최소 비용을 찾도록 도와주세요.

#5355 upload 5 done 3 how_to_reg 2

두 개의 헛간을 연결했더니 생긴 일 (Connecting Two Barns) timer 1s memory 256MB

#5355

두 개의 헛간을 연결했더니 생긴 일 (Connecting Two Barns) 1s 256MB