페이지 전환

인터넷이 발달하여 사람들이 웹서핑을 많이 하는데, 웹브라우져를 켜서 보통은 19번의 클릭을 한다고한다.

페이지를 전환하는 상태가 아래 그래프와 같이 주어진다면,

1번 페이지에서 2번, 3번, 4번 페이지로 갈 때의 가장 짧은 페이지 클릭 횟수는 1,1,2이고,

2번 페이지에서 1번, 3번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 3,2,1이고,

3번 페이지에서 1번, 2번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 1,2,3이고,

4번 페이지에서 1번, 2번, 3번 페이지로 가는 가장 짧은 페이지 클릭 횟수는 2,3,1이다.

이때, 가장 짧은 페이지 클릭 횟수의 합을 모두 구하면 1+1+2+3+2+1+1+2+3+2+3+1=22 이다.

이 그래프에서 모든 쌍은 1번에서 2번 페이지로 가기, 1번에서 3번 페이지로 가기, ..., 4번에서 3번 페이지로 가기,

12쌍이 나오기 때문에 어떤 페이지에서 다른 페이지로 이동하는 평균 클릭 횟수는 22/12로 1.833이된다.

입력

첫줄에 E(1≤E≤500)이 나온다.

다음줄부터 E개의 줄 각각에 i, j가 나오는데 이것은 i페이지에서 j페이지로 갈 수 있음을 의미한다.

또한 단 방향이므로, j에서 i로는 갈 수 없다. j에서 i로 갈 수 있으려면, 뒤의 줄에 j, i가 나와야 한다.

이때, 어떤 페이지에서 다른 페이지로 갈 수 없는 경우는 없도록 데이터가 입력된다.

또한 페이지의 번호는 1번 부터 i, j 값중 가장 큰 값이 페이지의 마지막 번호로 들어온다.

단, 페이지 번호는 500보다 작은 수이다.

출력

출력은 어떤 페이지에서 다른 페이지로 이동하는 평균 클릭 횟수를 출력한다.

출력값으로는 소수 넷째자리에서 반올림하여 소수 셋째자리까지 출력한다.

페이지 전환 1초 64MB