2016-17 Woburn Challenge Finals Round - Senior Division

Having fortunately gotten wind of the Cow-Bot's construction before meeting it in battle, the monkeys are in the process of frantically creating a virus, with the hopes of installing it into the robot and shutting it down! They've finished writing their program, which consists of ~N~ ~(1 \le N \le 300\,000)~ lines of code, but unfortunately its quality may be somewhat lacking…

At any point in time, each line of code either contains a bug, or doesn't. Initially, each line ~i~ contains a bug if ~B_i = 1~, and otherwise doesn't if ~B_i = 0~ ~(0 \le B_i \le 1)~.

Each minute, the monkeys can select one line of code which contains a bug, and fix that bug! Unfortunately, their code is so fragile that fixing some bugs may introduce others. If a bug is fixed on line ~i~, then if ~L_i = 0~, there are no consequences. Otherwise, one other line ~L_i~ ~(1 \le L_i \le N, L_i \ne i)~ will begin to have a bug (regardless of whether it already had one or not).

In order to efficiently proceed with making their viral code as correct as possible, the monkeys are interested in the answers to two questions. Firstly, what's the minimum possible number of lines of code which can be left containing bugs after they fix as many bugs as they'd like to? And secondly, how quickly can that minimum number of outstanding bugs be achieved? If ~Q = 1~, then you only need to answer the first of these questions, and if ~Q = 2~, then you must answer both.

In test cases worth ~5/30~ of the points, ~Q = 1~ and ~N \le 2\,000~.
In test cases worth another ~4/30~ of the points, ~Q = 1~.
In test cases worth another ~6/30~ of the points, ~N \le 2\,000~.

Input Specification

The first line of input consists of two space-separated integers ~N~ and ~Q~.
~N~ lines follow, the ~i~-th of which consists of two integers ~B_i~ and ~L_i~ (for ~i = 1 \dots N~).

Output Specification

If ~Q = 1~, then output a single integer - the minimum possible number of bugs which can remain in the code.
Otherwise if ~Q = 2~, then output two space-separated integers - the minimum possible number of bugs which can remain in the code, and the minimum number of minutes required to achieve that number of bugs.

Sample Input

10 2
1 4
0 0
0 8
0 10
0 0
1 0
1 4
1 4
1 5
0 7

Sample Output

1 6

Sample Explanation

One optimal sequence of lines to debug is: ~1, 6, 7, 8, 9, 5~.
After this sequence, the only line containing a bug will be line ~4~. It's impossible to eliminate all of the bugs from the monkeys' code (hopefully the same isn't true for yours…).