경기과학고에 두 개의 기숙사 ‘배요배’관과 ‘한요한’관이 생겼다. 

두 기숙사는 무한히 넓어서 많은 사람들이 들어갈 수 있다. 

처음에는 두 기숙사 모두 1~n까지의 번호가 매겨진 n명의 학생들이 각각 있었다. 

경기과학고 기숙사에서는 ‘거리적 사회두기’를 실시한다. 

사감쌤인 BYH는 학생들을 이동시켜려고 한다. 

BYH는 ‘배요배’관과 ‘한요한’관에서 절반의 학생을 교환해 다른 관으로 이동하기를 원한다. 하지만 같은 관에 있으면 문제가 되는 학생들이 있다. 

그래서 이 학생들을 같은 기숙사에 있지 못하게 거리적 사회두기를 실시한다.

예를 들어 ‘배요배’관의 3번 학생과 ‘한요한’관의 2번학생이 문제가 되는 학생의 쌍이라면, 두 학생은 같은 관에 있지 못한다. 

이러한 쌍이 총 m개 있을 때, BYH를 도와 이동할 수 있는 최대 인원수(‘배요배’관에서 k명, ‘한요한’관에서 k명이 이동할 때 k의 최댓값)를 구해야 한다. 

첫 번째 줄에 ‘배요배’관과 ‘한요한’관에 있는 학생 수 n과 문제가 되는 학생 쌍의 수 m이 주어진다.

2번째 ~ m+1번째 줄에 a, b의 형태로 문제가 되는 두 학생의 쌍이 입력된다.

a 학생은 ‘배요배’관의 a번째 학생, b 학생은 ‘한요한’관의 b번째 학생이다.

입력값의 범위

1 ≤ n ≤ 200

0 ≤ m ≤ 10000

1 ≤ a, b ≤ m

k(‘배요배’관과 ‘한요한’관에서 교환되는 학생 수)의 최댓값을 출력해야 한다. 

(k<=m/2, 예를 들어 n명 전체를 교환하는 등의 교환은 불가능하다.)

예시 설명

‘배요배’관의 6, 7, 8번 학생과 ‘한요한’관의 6, 7, 8번 학생이 교환되는 것이 최대이다.