문제

N$N$개의 정점을 가진 방향성 그래프가 있다. 각 그래프의 정점에 1$1$에서 N$N$까지의 번호가 매겨져 있다.
이 그래프에는 N \times (N-1)$N \times (N-1)$개의 간선이 존재하는데, 이는 임의의 서로 다른 두 정점을 연결하는 방향성 간선이 하나씩 있는 것이다. 이 간선을 이용해 x$x$번 정점에서 y$y$번 정점으로 이동하는 데에는 t_{x, y}$t_{x, y}$의 시간이 걸린다. 이 때 t_{x, y} \neq t_{y, x}$t_{x, y} \neq t_{y, x}$일 수도 있음에 유의하라.

또한, 각 정점에는 색이 칠해져 있다. 이 색은 모두 구분이 가능하며, N$N$가지의 색이 있다. 색에도 1$1$에서 N$N$까지의 번호를 붙이도록 한다. 초기에 i$i$번 정점에 색칠된 색의 번호를 C_i$C_i$라고 하자. 경근이는 x$x$번 정점에서 시작하여 그래프 위를 돌아다니며 정점에 칠해진 색을 바꾸려고 하는데, 그 과정은 다음과 같다 :

1. 모든 정점이 같은 색으로 칠해져 있다면 과정을 종료한다.
2. 만약 경근이가 현재 i$i$번 정점에 있다면, 다음에 이동할 정점으로 i$i$번 정점과는 다른 j$j$를 각각 \frac{1}{N - 1}$\frac{1}{N - 1}$의 확률로 선택한다.
3. i$i$번 정점의 색 C_i$C_i$를 p$p$의 확률로 색 C_j$C_j$로 칠한다.
4. 경근이가 j$j$번 정점으로 이동한다. 이 때 t_{i, j}$t_{i, j}$의 시간이 걸린다. 그 후, j$j$번 정점의 색 C_j$C_j$를 q$q$의 확률로 2번 단계에서의 C_i$C_i$로 칠한다. 1번 단계로 돌아간다.

경근이가 색칠하는 과정을 끝내기까지 걸리는 시간의 기댓값을 구하여라.