Check Path Presence

Determine whether the graph contains a path 1—2—…—N made of direct edges. All vertices must be visited in ascending order, and a detour through other vertices cannot replace the direct edge between consecutive numbers.

输入格式

This site's input: the first line contains N M (1≤N≤100000, 0≤M≤200000), followed by M lines, each describing a simple undirected edge u v, with vertices numbered 1..N.

输出格式

Output a single integer, the answer.

样例 1

输入：

4 5
1 2
2 3
4 1
4 3
3 1

输出：

1

样例 2

输入：

3 2
1 3
3 2

输出：

0

样例 3

输入：

1 0

输出：

1

样例说明

Example 1: 1—2, 2—3, and 3—4 all exist, so output 1.

Example 2: the direct edge 1—2 is missing, so even though the graph is connected the required walk is impossible; output 0.

Example 3: a single vertex already forms the path and needs no edges; output 1.