저항의 얽힘

이미지 출처: commons.wikimedia.org

평소와 마찬가지로 대회 직전의 KFFÍ는 모든 것이 엉망이다. 다른 사람들이 물건을 준비하는 일을 도우려고 HR에 도착하기 시작했을 때, Bjarki는 이미 와서 탁자 아래를 기어 다니고 있다. 왜 그러고 있느냐는 질문에 그는 물건들이 작동하도록 뒤엉킨 케이블을 정리하고 모든 것을 올바르게 연결하고 있다고 답한다. 하지만 많은 전선이 위험할 정도로 뜨거워지고 있어 무언가 조금 이상해 보인다. 문제는 물론 저항이다. 저항이 높을수록 열도 더 많이 발생한다. Bjarki가 탁자 아래에서 기어 나와 휴식을 취하는 동안, 이 뒤엉킨 케이블의 두 지점 사이 저항이 얼마인지 알아낼 수 있는가?

입력은 전선들이 만나는 지점들의 모음과 이 지점들 사이를 잇는 전선들로 주어진다. 각 전선에는 저항 $n \Omega$이 있으며, 여기서 $\Omega$은 측정 단위인 옴이다. 또한 저항을 측정할 두 지점도 주어진다. 다행히도 어떤 물리학과 학생이 교실에 필기 노트를 두고 갔으므로, 이를 계산하는 방법에 관한 몇 가지 정보를 얻을 수 있다.

규칙 1: 지점 $x, y$ 사이에 저항이 각각 $n \Omega$과 $m \Omega$인 서로 다른 두 전선이 있다면, 두 전선을 모두 저항이 $1/(1/n+1/m) \Omega$인 하나의 전선으로 바꿀 수 있다.

[h!]

규칙 1

규칙 2: 시작점도 끝점도 아닌 지점 $x$이 있다고 가정하자. 또한 $x$이 서로 다른 다른 두 지점 $a, b$에 정확히 하나의 전선씩으로 연결되어 있고, 그 전선들의 저항이 $n \Omega$과 $m \Omega$이라고 가정하자. 그러면 지점 $x$을 제거하고, 대신 $a$과 $b$을 저항이 $(n + m)\Omega$인 전선으로 연결할 수 있다.

[h!]

규칙 2

규칙 3: 시작점도 끝점도 아닌 지점 $x$이 있다고 가정하자. 또한 $x$이 서로 다른 다른 세 지점 $a, b, c$에 정확히 하나의 전선씩으로 연결되어 있고, 그 전선들의 저항이 순서대로 $n \Omega$, $m \Omega$, $l \Omega$이라고 가정하자. $s = (nm + nl + ml)$이라 하자. 그러면 지점 $x$을 제거하고, 대신 $a$과 $b$을 저항이 $s/l \Omega$인 전선으로 연결하고, $a$과 $c$을 저항이 $s/m \Omega$인 전선으로 연결하고, $b$과 $c$을 저항이 $s/n \Omega$인 전선으로 연결할 수 있다. 이 변환을 반대 방향으로 적용할 수도 있다.

[h!]

규칙 3

채점

그룹 | 점수 | 제한

1 | 30 | 답을 구하려면 규칙 1만 적용하면 된다.

2 | 30 | 답을 구하려면 규칙 2만 적용하면 된다.

3 | 30 | 답을 구하려면 규칙 1과 2만 적용하면 된다.

4 | 10 | 답을 구하려면 규칙 1, 2, 3만 적용하면 된다.

입력의 첫 줄에는 지점의 수와 전선의 수를 나타내는 두 정수 $2 \leq n \leq 100$과 $1 \leq m \leq 10^5$가 주어진다. 다음 줄에는 저항을 측정할 시작점과 끝점을 나타내는 서로 다른 두 정수 $1 \leq s, t \leq n$가 주어진다. 마지막으로 각각 세 정수 $1 \leq a, b \leq n$과 $1 \leq x \leq 1000$를 포함하는 $m$개의 줄이 주어진다. $a, b$은 서로 다르며 전선의 양 끝점을 나타내고, $x \Omega$은 전선의 저항이다. $s$에서 $t$까지 갈 수 있는 전선들의 연속이 항상 하나 이상 존재함이 보장된다. 어떤 전선을 지나는 $s$에서 $t$까지의 단순 경로가 하나도 없다면, 그 전선은 무시해도 된다. 단순 경로란 $s$에서 $t$까지 가는 도중 어떤 전선도 두 번 등장하지 않는 경로이다.

답은 항상 정수의 분수로 표현할 수 있음을 보일 수 있다. 답이 $p/q$이고 $p, q$이 완전히 약분되어 있다고 하자. $p, q$이 매우 커질 수 있으므로 $pq^{-1} \pmod{10^9 + 7}$을 출력한다. 여기서 역원은 모듈러 연산에 대한 역원이다.

첫 번째 예제는 그룹 1에 해당한다. 답은 $12/25$이다. $12 \cdot 25^{-1} \pmod{10^9 + 7}$은 $360000003$이다. 이는 $360000003 \cdot 25 \equiv 12 \pmod{10^9 + 7}$이기 때문이다. 설명 그림에서 각 화살표 옆의 숫자는 어떤 규칙이 적용되었는지를 나타낸다.

[h!]

예제 1

두 번째 예제는 그룹 2에 해당한다. $0$으로 표시된 첫 번째 화살표는 시작점에서 끝점까지 가는 어떤 단순 경로에도 포함되지 않는 전선들을 제거하는 것을 나타낸다.

[h!]

예제 2

세 번째 예제는 그룹 3에 해당한다. 답은 $20/11$이다. $20 \cdot 11^{-1} \pmod{10^9 + 7}$은 정확히 $363636368$이다.

[h!]

예제 3

네 번째 예제는 그룹 4에 해당한다. 규칙 $3$을 반대 방향으로 사용할 때 이를 $3'$으로 나타내자. 답은 $5/6$이고, $5 \cdot 6^{-1} \pmod{10^9+7}$은 $833333340$이다.

[h!]

예제 4