A tournament has n players, numbered 1 to n, and a list of m known rivalries. Each rivalry is a pair of players who insist on being placed on OPPOSITE teams if they both play. Determine whether there exists a way to split all n players into exactly two teams (every player assigned to one of the two) such that every rivalry pair ends up on opposite teams. Players with no listed rivalry may be placed on either team freely.
Input format
Line 1: two integers n and m — number of players (1-indexed) and number of rivalries.
Next m lines: two integers u v — an undirected rivalry between player u and player v (u ≠ v). The same rivalry may appear more than once.
Output format
A single integer: 1 if a valid two-team split exists, 0 otherwise.
Constraints
- 1 ≤ n ≤ 40
- 0 ≤ m ≤ 200
- 1 ≤ u, v ≤ n, u ≠ v