# What you can see by reading the article

--Understanding the solution of the article author's "ABC 103 D --Island War" --Understanding the author's approach to the algorithm problem

# This issue

** ABC 103 D --Island War ** → Click here for problem statement

``````from operator import itemgetter

# ==============================================================
# return:Output how many bridges should be removed when a request is given to prevent N islands and M islands from going back and forth.
# pre:  5 2
# 1 4
# 2 5
# post:　1 ->1 if only the bridge between 2 and 4 is removed,4 2,You will not be able to go back and forth between 5.
# ==============================================================

#★ step1 Question sentence N,Make M an int type and make it a variable
#★ step2 Given a,Sort the requests of b in ascending order of b
#                      ->Implementation:Remove the bridge between the given requests a b and make it inaccessible.
#                         idx a b
#                      -> 0:  1 3                  　1 2
#                         1:2 4 if 2,Exclude between 3 2 If 3 1,2 2,Exclude between 3
#                      ->Exclude one bridge if the next a is smaller than the previous b,Exclude two bridges if it is greater than or equal to the value of a next to the previous b
#                      ->Sort b in ascending order so that you can see the value of the previous b by the value of the next a to see if you want to remove the bridge.
#★ step3 Determine if the next value of a is greater than or equal to the previous value of b
#★ step4 If the value of the next a is greater than or equal to the value of the previous b, increment the number to be removed and update the value of the previous b with the current value of b.

#Get N and M
N, M = map(int, input().split())

#Index a for M islands,Get the requests that b does not come and go as an array
ab_requests =  [tuple(map(int, input().split())) for _ in range(M)]

#Sort in ascending order of b value
#Looking at the document, the key=itemgetter(num)Looks good-> https://docs.python.org/3/howto/sorting.html
ab_requests_sorted = sorted(ab_requests,key=itemgetter(1))

prev_b = -1
next_a = -1
removed_counts = 0

for a, b in ab_requests_sorted :
#Use as the next a
next_a = a
#Determine if the next value of a is greater than or equal to the previous value of b
#Larger case[(1,2),(3,4)]And the above cases[(1,2),(2,3)]Note
if prev_b <= next_a :
#Increment the number of bridges to remove
removed_count += 1
#Update the previous b so that you can compare the value with the next a
prev_b = b

#Output result
print(removed_count)

``````