n towns numbered 1 to n and a list of two-way roads roads, where roads[i] = [type, u, v] is a road between towns u and v. The type says who may drive on it:
- 1: only Anya;
- 2: only Boris;
- 3: both of them.
Close as many roads as possible while keeping it true that Anya and Boris can each get from any town to any other using only the roads open to them.
Return the maximum number of roads you can close. If even now one of them cannot reach every town, return -1.n=3, roads=[[3, 1, 2], [3, 2, 3], [1, 1, 3], [2, 1, 3]] → 2
The two shared roads already connect all three towns for both drivers, so both private roads can be closed.
n=4, roads=[[3, 1, 2], [1, 2, 3], [2, 2, 3], [1, 3, 4], [2, 3, 4], [1, 1, 3]] → 1
Anya can manage with roads 1–2, 2–3 and 3–4, so her road 1–3 can go. Every other road is needed, so only one can be closed.
n=3, roads=[[1, 1, 2], [1, 2, 3], [2, 1, 2]] → -1
Boris cannot reach town 3 at all, so the answer is −1.
n=3, roads=[[3, 1, 2], [3, 2, 3], [1, 1, 3], [2, 1, 3]]
2
Run checks the first 3 tests in your browser. Submit checks all 60 tests on the server, hidden ones included.