문제

\(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번 단계로 돌아간다.

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