Програмчлалын олимпиадын бодлогын архив

N ялгаатай өнгө өгөгдсөн ба өнгө бүрийн хувьд тэр өнгөөр будагдсан хайрцаг байна. Мөн эдгээр N өнгүүдээр будагдсан M ширхэг бөмбөлгүүдийг хайрцгуудад хийсэн. Ямар бөмбөлөг ямар хайрцагт байгаа нь мэдэгдэж байгаа. Хамгийн цөөндөө хэдэн үйлдлээр хайрцаг бүрд зөвхөн өөрийнх нь өнгөтэй ижил өнгийн бөмбөлгүүд үлдэхээр болгож болохыг ол. Нэг үйлдэл гэж хоёр бөмбөлгийн байрыг солих эсвэл нэг бөмбөлгийг өөр хайрцаг руу зөөхийг хэлнэ.

Input

N ба M (2 ≤ N ≤ 10, 1 ≤ M ≤ 100) тоонууд эхний мөрөнд зайгаар тусгаарлагдан өгөгднө. Дараагийн M мөрөнд бөмбөлгийн өнгө болон түүний байрлаж байгаа хайрцгийн өнгийг заасан хос тоо зайгаар тусгаарлагдан байрлана.

Output

Гаралт дээр хамгийн цөөн үйлдлийн тоог заасан бүхэл тоо байх ёстой

Example

Input:
4 8
1 3
2 4
3 2
4 1
2 4
1 1
2 4
3 4

Output:
6