Count Ordered Four-Shop Road Paths That Visit One Shop of Each Type

You need to buy school supplies at four different kinds of shop: a bookshop for a workbook, a school-supply shop for glue, a sports store for a pair of sneakers and a stationery store for a pencil. Your town has many shops of each kind, connected by roads. Before searching for the shortest route, you want to know how many routes there are, so you decide to count them.

Each shop's kind is encoded as an integer: 0 is a bookshop, 1 is a school-supply shop, 2 is a sports store and 3 is a stationery store. Given the kind of every shop and the roads between shops, return the number of valid paths. A valid path visits exactly one shop of each kind, in any order, moving along roads.

Function Signature

def count_paths(shops: list[int], roads: list[list[int]]) -> int:

shops[i] is the kind of the shop with index i. Each road [a, b] connects the shops with indices a and b.

Rules

• Roads are bidirectional: a road [a, b] can be travelled from a to b and from b to a.
• A valid path is an ordered list of four shop indices [p0, p1, p2, p3] such that shops[p0], shops[p1], shops[p2] and shops[p3] are 0, 1, 2 and 3 in some order, and there is a road between p0 and p1, between p1 and p2, and between p2 and p3.
• Every shop has one of the four kinds, so passing through any fifth shop would visit two shops of the same kind. A valid path therefore consists of exactly four shops, each joined to the next by a direct road.
• Order matters: the same four shops visited in two different orders are two different paths. In particular, a path and its reverse are counted separately.
• If some kind has no shop, or no four shops can be connected this way, return 0.

Constraints

• 1 <= len(shops) <= 50
• 0 <= shops[i] <= 3
• 0 <= len(roads) <= 250
• Each road is [a, b] with 0 <= a, b < len(shops) and a != b.
• There is at most one road between any two shops: the input never contains both [a, b] and [b, a], and never repeats a road.
• The answer is at most 50 * 49 * 48 * 47 = 5,527,200.

Examples

Example 1

Input: shops = [1, 0, 3, 2, 2], roads = [[0, 1], [1, 2], [1, 4], [2, 3], [2, 4]]
Output: 6

Shop 0 is the only school-supply shop, shop 1 the only bookshop and shop 2 the only stationery store; shops 3 and 4 are both sports stores. The valid paths are [0, 1, 2, 3], [0, 1, 2, 4] and [0, 1, 4, 2], plus their reverses [3, 2, 1, 0], [4, 2, 1, 0] and [2, 4, 1, 0].

Example 2

Input: shops = [0, 1, 2, 3], roads = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output: 8

The roads form a cycle through the four shops, one of each kind. A path can start at any of the four shops and go around the cycle in either direction, for example [0, 1, 2, 3] and [0, 3, 2, 1], which gives 4 * 2 = 8 paths.

Example 3

Input: shops = [0, 1, 1, 2], roads = [[0, 1], [1, 2], [2, 3], [0, 2]]
Output: 0

No shop is a stationery store (kind 3), so no valid path exists.