Hello Everyone!

https://mirror.codeforces.com/contest/845/problem/G

The problem says that we are given a weighted connected graph in which path length is defined as xor of all weights on the path. We are given two vertices and need to find shortest path length.

In the solution, we are calculating cycle basis of graph. For this we first make a spanning tree of the graph. Let's assume we have an empty set S. Then we take all the non-spanning edges of the graph one by one and find the cycle which this edge is making with only the spanning edges and include this cycle in our set S . The claim is that every set of cycles in the graph is a subset of this set S (We can also reduce S to its basis). I am unable to get this claim. Can somebody give me a proof of this of how is it including every cycle that exists in the graph

Thank You