No.3024 Bijective Shooting
p-adic
binapNote
The time limit for this problem is 5000[ms].
Problem Statement
First, you are given a positive integer $N$ and an integer $M$ that is at least $2$.
$N$ bots called Shooting-Loving Bots took part in a certain festival. They are numbered with the positive integers $i$ not exceeding $N$, and each is called Shooting-Loving Bot $i$.
A festival means a shooting gallery. The $N$ Shooting-Loving Bots all went to the same shooting gallery at once. In that shooting gallery, $M$ prizes are lined up on a stand in $1$ row from left to right, and for each positive integer $j$ not exceeding $M$, the $j$-th prize from the left is called prize $j$. If you fire a bullet at a prize lined up on the stand and hit it, that prize is knocked down to the floor.
Here, for every positive integer $i$ not exceeding $N$, Shooting-Loving Bot $i$ intends to fire a bullet at $1$ of the $2$ prizes, prize $X_i$ or prize $Y_i$ ($X_i$ and $Y_i$ are distinct positive integers not exceeding $M$), but it has only $1$ bullet.
Find the maximum total number of prizes that the $N$ Shooting-Loving Bots can knock down.
Input
The input is given from standard input in $1 + N$ lines in the following format:
- Line $1$ contains $N, M$ separated by a single space.
- For each positive integer $i$ not exceeding $N$, line $1+i$ contains $X_i,Y_i$ separated by a single space.
$N$ $M$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^5$.
- $M$ is an integer satisfying $2 \leq M \leq 10^{18}$.
- For every positive integer $i$ not exceeding $N$, $X_i, Y_i$ are integers satisfying $1 \leq X_i < Y_i \leq M$.
Output
Print on $1$ line the maximum total number of prizes that the $N$ Shooting-Loving Bots can knock down.
Print a newline at the end.
Sample
Sample 1
Input
1 2 1 2
Output
1
There is only $1$ Shooting-Loving Bot. Shooting-Loving Bot $1$ intends to fire at prize $1$ or prize $2$, but since it has only $1$ bullet, it can knock down only $1$ of them.
For those familiar with set theory: in the above situation, looking at the correspondence of which Shooting-Loving Bot knocked down which prize gives an injection that is not a surjection, from the set of all non-negative integers not exceeding $N = 1$ to the set of all non-negative integers not exceeding $M = 2$.
Sample 2
Input
2 3 1 2 1 2
Output
2
There are $2$ Shooting-Loving Bots. Both intend to fire at prize $1$ or prize $2$, and neither will fire at prize $3$. By each firing at a different prize and hitting it, they can knock down a total of $2$ prizes.
For those familiar with set theory: in the above situation, looking at the correspondence of which Shooting-Loving Bot fired at which prize gives an injection that is not a surjection, from the set of all non-negative integers not exceeding $N = 2$ to the set of all non-negative integers not exceeding $M = 3$.
Sample 3
Input
3 2 1 2 1 2 1 2
Output
2
There are $3$ Shooting-Loving Bots. All of them intend to fire at prize $1$ or prize $2$. For example, if some $2$ of them fire at the same prize and one of their bullets hits, and the remaining $1$ bot fires at the other prize and hits, they can knock down a total of $2$ prizes.
For those familiar with set theory: in the above situation, looking at the correspondence of which Shooting-Loving Bot fired at which prize gives a surjection that is not an injection, from the set of all non-negative integers not exceeding $N = 3$ to the set of all non-negative integers not exceeding $M = 2$.
Sample 4
Input
3 3 1 3 1 3 1 3
Output
2
There are $3$ Shooting-Loving Bots. All of them intend to fire at prize $1$ or prize $3$, and none will fire at prize $2$. For example, if some $2$ of them fire at the same prize and one of their bullets hits, and the remaining $1$ bot fires at the other prize and hits, they can knock down a total of $2$ prizes.
For those familiar with set theory: in the above situation, looking at the correspondence of which Shooting-Loving Bot fired at which prize gives a map that is neither a surjection nor an injection, from the set of all non-negative integers not exceeding $N = 3$ to the set of all non-negative integers not exceeding $M = 3$.
Sample 5
Input
3 3 1 2 2 3 1 3
Output
3
There are $3$ Shooting-Loving Bots. Shooting-Loving Bot $1$ intends to fire at prize $1$ or prize $2$, Shooting-Loving Bot $2$ intends to fire at prize $2$ or prize $3$, and Shooting-Loving Bot $3$ intends to fire at prize $1$ or prize $3$. For example, if for every positive integer $i$ not exceeding $N = M = 3$, Shooting-Loving Bot $i$ fires at prize $i$ and hits it, they can knock down a total of $3$ prizes.
For those familiar with set theory: in the above situation, looking at the correspondence of which Shooting-Loving Bot fired at which prize gives a bijection from the set of all non-negative integers not exceeding $N = 3$ to the set of all non-negative integers not exceeding $M = 3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。