페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5355

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

문제

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

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

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


입력

각 테스트 케이스의 입력은 T 개의 하위 테스트 케이스(1≤T≤20)를 포함하며 전체 테스트 케이스를 통과하려면 모든 하위 테스트 케이스에 올바르게 응답해야 합니다.
입력의 첫 번째 줄에는 T 하위 테스트 케이스가 뒤따르는 T가 포함됩니다.
각 하위 테스트 케이스의 첫 번째 줄에는 두 개의 정수 N과 M이 있습니다. 각각 두 개의 정수 i와 j를 포함하는 다음 M 라인은 두 개의 다른 필드 i와 j를 연결하는 도로를 나타냅니다. 입력은 두 필드 사이에 최대 하나의 도로가 있고 모든 하위 테스트 케이스에 대한 N+M의 합이 5⋅105를 초과하지 않음을 보장합니다.​

출력

출력 T 라인. i번째 줄에는 i번째 하위 테스트 케이스의 최소 비용인 정수가 포함되어 있습니다.


예제1

입력
2

5 2

1 2

4 5

5 3

1 2

2 3

4 5
출력
2

1


출처

USACO 2021 December Silver

역링크 공식 문제집만