Official Analysis

Explanation

While the official editorial starts from the beginning and end of the graph and tries to work its way to a common node or edge, it's also possible to start from the common location and try to get to the beginning and end.

Implementation

Time Complexity: $\mathcal{O}(M^2)$

Copy
from collections import deque

node_num, edge_num = [int(i) for i in input().split()]
neighbors = [[] for _ in range(node_num)]
for _ in range(edge_num):
	n1, n2, c = input().split()
	n1 = int(n1) - 1
	n2 = int(n2) - 1
	neighbors[n1].append((n2, c))
	neighbors[n2].append((n1, c))