An electrician wired up n junction boxes, numbered 1 to n, using m wires. Each wire connects two DIFFERENT junction boxes, and no two wires connect the exact same pair of boxes. The wiring may or may not be fully connected.

A loop exists if some junction box can reach itself again by following two or more distinct wires without immediately reusing the wire it just came from. Determine whether the wiring contains at least one loop anywhere.

Input format

Line 1: two integers n and m — number of junction boxes (1-indexed) and number of wires. Next m lines: two integers u v — an undirected wire between junction box u and box v (u ≠ v). No unordered pair {u, v} appears more than once.

Output format

A single integer: 1 if the wiring contains a loop, 0 otherwise.

Constraints

• 1 ≤ n ≤ 40
• 0 ≤ m ≤ 40
• 1 ≤ u, v ≤ n, u ≠ v, no duplicate pairs

4 4
1 2
2 3
3 4
4 1

1

4 3
1 2
2 3
3 4

0