[Solution] Sweepstake solution codeforces | Kotlin Heroes: Episode 8

Sweepstake solution codeforces


Kotlin Heroes competition is nearing completion. This time nn programmers took part in the competition. Now organizers are thinking how to entertain spectators as well. One of the possibilities is holding sweepstakes. So for now they decided to conduct a survey among spectators.

Sweepstake solution codeforces

In total, organizers asked mm viewers two questions:

  1. Who will take the first place?
  2. Who will take the last place?

After receiving answers, organizers ranked all spectators based on the number of programmers they guessed right. Suppose, there are c2c2 viewers who guessed right both first and last place, c1c1 viewers who guessed either first or last place right and c0c0 viewers who didn’t guess at all. All c2c2 viewers will get rank 11, all viewers with one right answer will get rank c2+1c2+1 and all remaining viewers — rank c2+c1+1c2+c1+1.

You were one of the interviewed spectators. Also, as one of the organizers, you have access to survey results, but not to competition results. Calculate, what is the worst rank you can possibly get according to organizers’ ranking system?

Sweepstake solution codeforces

Input

The first line contains two integers nn and mm (2n10002≤n≤10001m21051≤m≤2⋅105) — the number of programmers participating in the competition and the number of surveyed spectators.

Next mm lines contain answers of spectators. The ii-th line contains two integers fifi and lili (1fi,lin1≤fi,li≤nfilifi≠li) — the indices of programmers who will take the first and last places in opinion of the ii-th viewer.

For simplicity, you are the first among spectators, so your answers are f1f1 and l1l1.

Output

Print the single integer — the worst rank among spectators you can possibly get according to organizers’ ranking system (bigger rank — worse, of course).

Sweepstake solution codeforces

Examples
input

Copy
2 3
1 2
2 1
2 1
output

Copy
3

Sweepstake solution codeforces


input

Copy
3 6
3 1
3 2
2 1
3 2
3 2
3 1
output

Copy
4

Sweepstake solution codeforces


Note

In the first example, if the second programmer takes first place, while the first programmer takes last place, you’ll have 00 right answers while the other two spectators — 22 right answers. That’s why your rank (in the worst case) will be c2+c1+1c2+c1+1 == 2+0+1=32+0+1=3.

In the second example, for example, if the third programmer takes the first place and the second programmer takes the last place, then you’ll have 11 right answer. The spectators 2244 and 55 will have 22 right answers, spectator 66 — 11 right answer and spectator 33 — 00 right answers. As a result, your rank will be equal to c2+1c2+1 == 3+1=43+1=4. (Note that spectator 66 will have the same rank 44).


Sweepstake solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment