Two teams, or an odd cycle

There are n people, numbered 0 to n − 1. Each edge (u, v) joins two people who must be on different teams. If two teams are possible, return (True, side), where side is a list of n numbers, each 0 or 1, and every edge joins a 0 to a 1.

If two teams are impossible, prove it: return (False, cycle), where cycle lists an odd number of different people, each joined by an edge to the next, and the last joined to the first (lesson 6).

two_teams(5, [(0, 1), (1, 2), (2, 3), (3, 0), (3, 4)])
# (True, [0, 1, 0, 1, 0])
two_teams(3, [(0, 1), (1, 2), (2, 0)])
# (False, [0, 1, 2])

Any correct answer is accepted. The tests check every edge of your teams, or follow your cycle and count its people. No edge joins a person to themselves; an edge may be listed twice.

Limits

• Up to 100,001 people and 170,000 edges.
• Paths and cycles can be 100,000 people long, so a recursive search is too deep. The big tests have 3 seconds each.