P3163 [CQOI2014] Dangerous Bridges

Alice and Bob live in a country consisting of $N$ islands, numbered from $0$ to $N-1$. Some pairs of islands are connected by bridges. The roads on the bridges are bidirectional, but only one person can pass at a time. Some bridges have become dangerous due to age and can be used at most twice. Alice wants to make $a_n$ round trips between islands $a_1$ and $a_2$ (a round trip means going from $a_1$ to $a_2$ and then back from $a_2$ to $a_1$). Meanwhile, Bob wants to make $b_n$ round trips between islands $b_1$ and $b_2$. During the whole process, each dangerous bridge can be used at most twice in total, while the other bridges can be used infinitely many times. Can Alice and Bob fulfill their wishes?

There are multiple test cases. For each test case, the first line contains seven space-separated integers: $N$, $a_1$, $a_2$, $a_n$, $b_1$, $b_2$, $b_n$. Then follows an $N$-by-$N$ symmetric matrix of uppercase letters. The entry at row $i$ and column $j$ describes the connection between islands numbered $i-1$ and $j-1$: if it is `O`, there is a dangerous bridge; if it is `N`, there is a normal bridge; if it is `X`, there is no bridge.

For each test case, output one line. Output “Yes” if they can both fulfill their wishes, otherwise output “No” (without quotes).

Constraints: For all testdata, $4 \leq N \leq 50$, $0 \leq a_1, a_2, b_1, b_2 \leq N-1$, $1 \leq a_n, b_n \leq 50$. Translated by ChatGPT 5