산유국

아제르바이잔은 지하자원이 풍부한 나라로 석유가 생산되어 국민들은 휘발유를 아주 저렴하게 사용할 수 있다. 아제르바이잔의 수도 바쿠에는 $N$개의 교차로와 $M+N-1$개의 양방향 도로가 있다 바쿠는 남북으로 길이가 긴 도시이다. 교차로는 남북 방향으로 일직선으로 늘어서 있는데, 제일 북쪽 교차로에서 시작하여 $1$번부터 $N$번까지 번호가 붙어 있다. 도로는 오래된 도로와 신설 도로들이 있다. $N-1$개의 오래된 도로는 각 $i$ ($1 \le i < N$)에 대해서 $i$번 교차로와 $i+1$번 교차로를 연결한다. $M$개의 신설 도로는 각각 오래된 도로로 연결되지 않은 서로 다른 교차로 두 개를 연결한다. 한 쌍의 교차로를 연결하는 도로는 최대 $1$개이다.

수도 바쿠는 재정이 최근 좋지 않아 도로 중 일부에 톨게이트를 설치해서 통행료를 받기로 했다. 너무 많은 도로에서 통행료를 받으면 시민들의 불만이 생길 수 있으므로 정확히 $2$개의 도로에서 통행료를 받을 것이다. 통행료는 차 한 대가 톨게이트를 한번 지나갈 때 마다 $1$마나트(아제르바이잔 화폐 단위)를 받는다. 한 자동차가 톨게이트 두 개를 지나간다면, 두 번 모두 통행료를 내야 한다.

모든 교차로에는 각각 $N-1$대의 자동차가 있다. 한 교차로의 자동차들은 모두 현재 위치한 교차로가 아닌 서로 다른 교차로로 갈 것이다. 교차로 $u$에서 교차로 $v$로 갈 때, 운전자는 최소의 통행료를 내는 경로를 선택한다. (이 나라는 휘발유가 저렴하다.)

모든 자동차들이 자신의 목적지로 이동했을 때, 가장 많은 통행료를 받을 수 있는 두 도로를 알아내는 프로그램을 작성하라.

여러분은 다음 함수를 작성하여야 한다.

• long long findEdges( int N, int A[], int B[] ) ; 최초에 한번만 호출되는 함수이다. 교차로와 도로들의 형태를 알려준다. $N$은 교차로의 개수이다. $A$와 $B$는 각각 크기 $M$인 배열(vector)이다. 교차로 $A\[i]$번과 교차로 $B\[i]$번이 신설 도로로 이어져 있다는 의미이다. 단, $i$는 $0$ 이상 $M-1$ 이하이다. 주어진 교차로와 도로 상황에서 두 개의 도로에 톨게이트를 만들어서 받을 수 있는 가장 많은 통행료의 값을 리턴해야 한다.