ORIGINAL CODING QUESTION

Can the network form two teams?

Print 1 if vertices can be colored with two colors so every undirected edge joins different colors; otherwise 0. Self-loops invalidate it.

Open practice workspace

Original exercise · medium. Editorial role relevance does not imply a company has asked this question.

Input and output

n m, then m vertex pairs (u,v). Vertices are zero-based.

Constraints

1 ≤ n ≤ 30; 0 ≤ m ≤ 100; vertex IDs in [0,n).

Example 1

Input

3 2 0 1 1 2

Output

A path permits two teams.

Example 2

Input

3 3 0 1 1 2 2 0

Output

An odd cycle prevents two teams.

Explain your approach

Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?

Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.

Hint 1

Start a coloring search in every component.

Hint 2

Adjacent vertices need opposite colors.

Hint 3

A same-color edge witnesses an odd-cycle conflict.

Practice this question

Save your work privately, explain decisions and return to your revision queue.

Open practice workspace Browse the question library →