Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

B. Beguiling Your Boss
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Image by Joost J. Bakker, from commons.wikimedia.org

You have just started at the Nordic Cargo Permuting Company, whose business is moving cargo between its $$$k$$$ cargo bays.

Your boss has handed you today's work order: a list of $$$n$$$ cargo swaps. Each swap names two bays, and carrying it out means exchanging the cargo in those two bays. The swaps are to be carried out in the order listed. Your boss is adamant that every swap is carried out as written, for various paperwork reasons.

You wonder whether the work order could be shortened. A section of the list consists of the swaps at list positions $$$\ell$$$ through $$$r$$$, for some $$$1 \leq \ell \leq r \leq n$$$.

A section is redundant if skipping it makes no difference: carrying out only the swaps outside the section, in the order listed, leaves every piece of cargo in the same bay as carrying out the entire list does.

You are sure your cutting and gluing skills are up to the task of removing a redundant section from the work order. But how many sections are redundant?

Input

The input consists of:

  • One line with two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$2 \leq k \leq 10^6$$$), the number of cargo swaps and the number of cargo bays.
  • $$$n$$$ lines, each containing two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq k$$$, $$$a \neq b$$$), a request to swap the cargo in bays $$$a$$$ and $$$b$$$. The swaps are given in the order listed in the work order.
Output

Output the number of redundant sections.

Examples
Input
6 3
1 2
2 3
1 2
2 3
1 2
2 3
Output
1
Input
4 2
1 2
1 2
1 2
1 2
Output
4
Input
3 4
1 2
3 4
1 3
Output
0