408856: GYM103351 F Nomadic Life

There are $$$n$$$ cities in Tima's country. Some of them (usually cities located in Southern areas) are considered warm, while others (usually cities located in Northern areas) are very cold.

Tima is a real nomad and he feels himself obliged to switch places during different seasons. He will switch his living place exactly $$$4$$$ times during the year — one time in spring, summer, fall and winter.

Since springs and summers are very hot in warm cities, Tima wants to live in a cold place during these seasons. Similarly, since falls and winters are very freezing in cold cities, Tima wants to live in a warm place during these seasons.

He can only afford flights between $$$m$$$ pairs of cities though. He does not have much money to afford living in $$$5$$$ or more cities, so he wants to choose exactly $$$4$$$ cities $$$(a, b, c, d)$$$ that will satisfy his needs for the upcoming $$$5$$$ years. Since Tima is a nomad, all those cities should be distinct. How many different choices does he have?

Please note that a choice $$$(a, b, c, d)$$$ is not the same as $$$(b, a, d, c)$$$ or other its permutations.

First line of the input contains two integers $$$n$$$ and $$$m$$$ — the number of cities in Tima's country and the number of flights Tima can afford ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$).

Second line contains a binary string $$$s$$$ of length $$$n$$$. $$$s_i = 1$$$ indicates that $$$i$$$-th city is warm. Respectively, $$$s_i = 0$$$ indicates that $$$i$$$-th city is cold.

Next $$$m$$$ lines each contain a pair of integers $$$a_i$$$ and $$$b_i$$$ which indicates that Tima can afford a flight between cities $$$a_i$$$ and $$$b_i$$$ in both directions ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$). It is guaranteed that no pair of cities appears twice in the input.

Output a single integer — the number of different choices Tima has.

5 7
11100
1 2
1 3
2 4
3 5
4 5
1 5
5 2

2

There are exactly two choices for Tima in the sample:

1. $$$(4, 5, 1, 2)$$$. Both cities $$$4$$$ and $$$5$$$ are cold, both cities $$$1$$$ and $$$2$$$ are warm. Tima can afford all seasonal flights $$$4 - 5$$$, $$$5 - 1$$$, $$$1 - 2$$$, $$$2 - 4$$$.
2. $$$(5, 4, 2, 1)$$$. Both cities $$$5$$$ and $$$4$$$ are cold, both cities $$$2$$$ and $$$1$$$ are warm. Tima can afford all seasonal flights $$$5 - 4$$$, $$$4 - 2$$$, $$$2 - 1$$$, $$$1 - 5$$$.

Note that $$$(5, 3, 1, 2)$$$ does not count as a valid choice since $$$3$$$ is a warm city thus it is not suitable for summer.