Graph Isomorphism Check

You are given two undirected weighted graphs, each with N nodes (numbered from 0 to N-1) and M edges. Each edge is described by three integers u, v and w, which indicates that there is an edge between node u and node v with weight w. Note that the graphs are undirected: an edge represented as (u, v, w) is considered identical to (v, u, w).

Two graphs are isomorphic if, after converting every edge to a normalized form (min(u, v), max(u, v), w) and sorting the list of edges, the two graphs have exactly the same edge list (including the corresponding weights).

Your task is to check if the two given graphs are isomorphic. Output True if they are, and False otherwise.

The normalization process can be summarized by the formula: $$ (u,v,w) \to \big(\min(u,v),\,\max(u,v),\,w\big). $$

inputFormat

The input is read from standard input (stdin) and has the following format:

N M
u1 v1 w1
u2 v2 w2
... (M lines for the first graph)
u1' v1' w1'
u2' v2' w2'
... (M lines for the second graph)

Here, the first line contains two integers N and M. The next M lines describe the edges of the first graph, and the following M lines describe the edges of the second graph.

outputFormat

Output to standard output (stdout) a single line containing True if the two graphs are isomorphic, and False otherwise.

4 5
0 1 10
1 2 20
2 3 30
3 0 40
0 2 50
3 2 30
2 1 20
1 0 10
0 3 40
0 2 50

True