문제

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

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

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

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