https://atcoder.jp/contests/agc035/tasks/agc035_bWe can restated the problem as follows. There are people on vertices with odd degree. When we swap the direction of the edge, the human on the end-points moves on the edge. If both endpoints…