산유국

아제르바이잔은 지하자원이 풍부한 나라이다. 석유 생산량이 많아 국민들은 휘발유를 아주 싸게 쓸 수 있다.

수도 바쿠에는 $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$ 이하이다. 주어진 교차로와 도로 상황에서 두 개의 도로에 톨게이트를 만들어 받을 수 있는 통행료의 최댓값을 리턴해야 한다.