n городов с номерами от 1 до n и список двусторонних дорог roads, где roads[i] = [type, u, v] — дорога между городами u и v. Тип дороги определяет, кто может по ней ездить:
- 1 — только Аня;
- 2 — только Борис;
- 3 — оба.
Нужно закрыть как можно больше дорог так, чтобы и Аня, и Борис по-прежнему могли добраться из любого города в любой, пользуясь только своими доступными дорогами.
Верните максимальное число дорог, которые можно закрыть. Если уже сейчас хотя бы один из них не может объехать все города, верните -1.n=3, roads=[[3, 1, 2], [3, 2, 3], [1, 1, 3], [2, 1, 3]] → 2
Две общие дороги уже связывают все три города для обоих, поэтому обе личные дороги можно закрыть.
n=4, roads=[[3, 1, 2], [1, 2, 3], [2, 2, 3], [1, 3, 4], [2, 3, 4], [1, 1, 3]] → 1
Аня обходится дорогами 1–2, 2–3 и 3–4, поэтому её дорогу 1–3 можно закрыть. Остальные нужны: закрыть удаётся только одну.
n=3, roads=[[1, 1, 2], [1, 2, 3], [2, 1, 2]] → -1
Борис не может добраться до города 3, так что ответ −1.
n=3, roads=[[3, 1, 2], [3, 2, 3], [1, 1, 3], [2, 1, 3]]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 60 тестов на сервере, включая скрытые.