Informatica Online Judge

  현의 교점의 개수 구하기 #2 [2364 / 093C]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 19   Total Tried : 19


The Champion of this Problem (C++) : gs18080 - ms / 657byte
My Best Submission (C++) : N/A

[35th 공병규 (gs17005)]
Writer ID : [gs17005]

Background

교준이에 의해 이세계로 가는 포탈을 타고 마계에 온 민제는 지낼 곳이 없어 친구 동현이의 집에 몰래 들어가게 된다.
그러다 장난끼가 발동한 민제는 자고 있는 동현이의 얼굴에 낙서를 하려고 한다. 먼저 동현이의
얼굴형은 원으로 가정할 수 있으며, 민제는 원의 둘레 위에 서로 다른 위치의 점 n개를 찍은 뒤
각 점에 시계방향으로 임의의 점부터 인덱스를 1~n으로 매길 것이다. 그 후 두 점을 잇는 m개의
현을 그어서 낙서를 한 뒤 현과 현의 교점의 총 개수로 낙서의 예술점수를 평가한다.

이 때 민제의 낙서의 정보가 주어질 때 낙서의 예술점수를 출력하시오.
(단, 한 점에서 3개 이상의 현이 만나는 경우는 없다고 가정한다.
또한 원 둘레 위의 각 점은 많아야 한 개의 현에 연결되어있다. )

Input

4<=n<=2000000

1<=m<=[n/2]


첫번째 줄에 n과 m이 차례대로 주어진다.
두번째 줄부터 m+1줄까지 현이 잇는 두 점의 인덱스 a,b가 주어진다. (1 <= a, b <= n)

Output

주어진 낙서의 예술점수를 출력하시오.

IO Example

Example Input
6 3
1 4
6 3
2 5 //수정됨 by gs17003 고동현

Example Output
3

Example Description
아래 그림에서 볼 수 있듯이 현의 교점의 개수는 3개이다.



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]