In Codeforces Round 1007 (Div. 2), I solved 2071C - Trapmigiano Reggiano using the following approach:

- Store the path from start to end node.
- Do DFS from start node and store the depths of all nodes.
- Sort the nodes with respect to descending order of their depths.
- Add the nodes to the result, one by one, from the highest depth to the lowest. However, during this process, skip all the nodes which are present in the path from start to end node (start and end nodes inclusive). The path nodes can be easily maintained using a set.
- In the end, add the path from start to end node to the result.

I deduced this solution simply through various examples and found out that it works. However, I'm not being able to derive a formal proof for it. If anyone can do so, it would be much appreciated. Thanks!

My submission: 308504994