문제
정올시 할인 마트에서는 고가의 전자 제품을 선착순으로 공짜로 나누어주는 초대형 이벤트를 진행하고 있다. 이 이벤트에 참여하기 위해 N명의 주부들이 한 줄로 서 있다.
처음에는 1번에서부터 N번 주부까지 차례대로 줄을 서 있었지만 주부들이 공짜에 눈이 멀었기 때문에 줄에서 이탈을 많이 한다. 여기에서 이탈이란 주부 A가 주부 B의 바로 앞에 끼어드는 행동을 말한다.
주부들은 이탈을 할 때 현재의 위치보다 앞에 끼어드는 경우도 있지만 실수로 더 뒤에 끼어드는 경우도 발생한다.
행사관계자인 당신은 이탈 중에서 주부 B가 주부 A보다 앞에 있었던 경우 즉, 주부 A가 주부 B의 앞으로 끼어들었을 때 원래의 순서가 서로 바뀌는 경우를 새치기라고 정하고 총 M번의 이탈 중 새치기가 몇 번 있었는지 알아내야한다.
입력
첫 번째 줄에는 N, M(2≤N≤100,000, 1≤M≤100,000)이 주어진다.
두 번째 줄부터 M개의 줄에는 A, B가 주어지는데, 주부 A가 주부 B 바로 앞에 끼어드는 행동을 말한다. 이 때, A와 B는 다르다.
[제약조건]
전체 데이터의 60%는 2 ≤ N ≤ 5,000, 1 ≤ M ≤ 5,000이다.
출력
입력된 이탈들 중 새치기의 수를 출력한다.
예제
5 6
3 5
5 1
4 2
3 1
2 5
1 4
4
힌트
출처
functionx
로그인해야 코드를 작성할 수 있어요.