问题描述

某广播公司要在一个地区架设无线广播发射装置。该地区共有 $n$ 个小镇，每个小镇都要安装一台发射机并播放各自的节目。

不过，该公司只获得了 FM104.2 和 FM98.6 两个波段的授权，而使用同一波段的发射机会互相干扰。已知每台发射机的信号覆盖范围是以它为圆心，$20$ $\tt km$ 为半径的圆形区域，因此，如果距离小于 $20$ $\tt km$ 的两个小镇使用同样的波段，那么它们就会由于波段干扰而无法正常收听节目。现在给出这些距离小于 $20$ $\tt km$ 的小镇列表，试判断该公司能否使得整个地区的居民正常听到广播节目。

输入格式

第一行为两个整数 $n$，$m$，分别为小镇的个数以及接下来小于 $20$ $\tt km$ 的小镇对的数目。

接下来的 $m$ 行，每行 $2$ 个整数，表示两个小镇的距离小于 $20$ $\tt km$（编号从 $1$ 开始）。$1 ≤ n ≤ 10000$，$1 ≤ m ≤ 30000$。

输出格式

如果能够满足要求，输出 $1$，否则输出 $-1$。

4 3
1 2
1 3
2 4

1