Two-operator split: hints, no solution

A city wants two transport operators, A and B, to share its n stations, numbered 0 to n - 1. Each row of lines joins two different stations. To avoid clashes, the two ends of every line must be handed to different operators.

Decide whether every station can be assigned to exactly one operator so that no line joins two stations of the same operator. Return true if such an assignment exists and false otherwise. Stations with no lines can go to either operator, and the map may consist of several separate parts, each of which must work on its own.

Examples

Input

n = 4, lines = [[0, 1], [1, 2], [2, 3]]

Output

true

Note

Give stations 0 and 2 to A and stations 1 and 3 to B.

Input

n = 3, lines = [[0, 1], [1, 2], [2, 0]]

Output

false

Note

Three stations that are pairwise joined cannot be split between two operators.

Input

n = 5, lines = [[0, 1], [2, 3]]

Output

true

Note

Station 4 has no lines and the two remaining lines are independent, so any split of each pair works.

Constraints

• 1 <= n <= 60000
• 0 <= lines.length <= 60000
• Every line joins two different stations in the range 0 to n - 1
• The same pair may be listed more than once

Hint 1: a nudge

Suppose you hand one station to operator A. What does that force for each station it is joined to, and what does that in turn force for their neighbours?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing