题目来源于USACO月赛，数据范围有所加强

题目概述

项目名称	排序	录制	#加法解释	#新挑战*
文件名	sort.*	record.*	interpreter.*	challenge.*
时间限制	2s	1s	1s	5s
空间限制	512MB	512MB	512MB	N/A
测试点数量	20	10	14	3
测试点分值	5	10	7~8	N/A
额外的编译选项	-O2			-O2 …
类型	传统	传统	传统	交互
比较方式	全文	SPJ	全文	全文
部分分	无	有	无	无

注意事项

所有题目中程序允许创建临时文件(仅供参考)。在C/C++中建议使用tmpfile函数创建临时文件，在关闭文件后将自动删除。

#include<stdio.h>
FILE *tmpfile( void );
//C
#include<cstdio>
std::FILE* std::tmpfile();
//C++

新挑战*为附加题，同时测试交互题的情况。
对于#标的题，请注意常数因子对于程序效率的影响(标程最长运行时间超过时限的一半)。

1.排序

题目描述

有n($n\le50000$)个物品，编号为$1\ldots n$，物品i的重量为$w_i$，每个物品的重量各不相同。现在需要对这n个物品按照重量排序，已经用天平进行了m($m\le200000$)次比较，一次比较结果用(i,j)表示。求至少再进行多少次比较才能完成排序。

输入格式

第一行两个整数n,m

接下来m行，每行两个整数i,j，表示$w_i>w_j$

输出格式

一个整数表示至少再进行多少次比较才能完成排序，如果给出的条件自相矛盾输出-1

输入样例

输出样例

3

样例解释

有5个物品，已经比较了5次。因为$w_2>w_1>w_5,w_2>w_3>w_4$，所以物品2是最重的。但是，还需要比较物品1和物品3的重量，才能知道第二重的物品。同理，还需要比较物品4和物品5，物品5和物品3，才能完成排序。

数据范围

对于30%的数据，$n\le500,m\le5000$
对于60%的数据，$n\le3000$
对于100%的数据，$n\le50000,m\le200000$

2.录制

题目描述

一场运动会中有n($n\le100000$)个项目需要录制，编号为$1\ldots n$，其中第i个项目的时间$s_i\ldots t_i(0\le s_i\le t_i\le10^9)$。现在有k($k\le n$)台录像机，编号为$1\ldots k$，两个项目i,j可以被同一台录像机录制，仅当$s_j\ge t_i$。求出最多可以录制的项目数量，并任意输出一种可行解(有SPJ)。

输入格式

第一行两个整数n,k

接下来n行，每行两个整数$s_i,t_i$

输出格式

第一行一个整数，表示最多可以录制的项目数量

接下来k行，第一个整数t表示该台录像机录制的项目数量，接下来t个整数表示该台录像机录制的项目编号

注意：项目编号应该按时间升序输出

输入样例

输出样例

4
2 4 2
2 1 3

样例解释

有6个项目，2台录像机。最多只能录制4个项目，比如在第一台录像机上录制项目2、4，在第二台录像机上录制项目1、3.需要注意的是，解不唯一，如交换两台录像机录制的项目也是可行解。

数据范围

测试点编号	n的范围	k的范围
1	$n\le10$	k=1
2	$n\le150$	k=1
3	$n\le100000$	k=1
4	$n\le150$	k=2
5	$n\le100000$	k=2
6	$n\le1000$	$k\le10$
7	$n\le100000$	$k\le10$
8	$n\le10$	$k\le n$
9	$n\le100000$	$k\le n$
10	$n\le100000$	$k\le n$

部分分

如果你的答案不正确，得分为0
如果你的答案正确，但没有输出可行解或可行解错误，得分为5
如果你的答案正确，且输出正确的解，得分为10

3.加法解释

题目描述

PL/S是一种简单高效的语言，有两个主要的功能：加法和循环。由于多次加法可能会溢出，因此规定所有加法运算都对$10^9+7$取模。更加高级的是循环功能，能够执行一段代码若干次。当然，循环是可以嵌套的。

现在给出一个PL/S语言的源代码，请输出其执行结果。

输入格式

给出的PL/S代码不超过100行，每行不超过350个字符。PL/S语言有三种语句(注意空格)：

<variable> = <expression>

<literal> LOOP {
  <list of statements>
}

PRINT <variable>

有三种类型的表达式：

<literal>

<variable>

<expression> + <expression>

其中variable是长度不超过10的变量名，全部为小写字母。

literal是不超过100000的正整数。

数据保证没有变量在定义前被使用，PRINT语句只出现在程序最后一行。

习惯上语法描述均不翻译

输出格式

一个正整数表示PRINT语句后变量的值。

输入样例

#1:
x = 1
10 LOOP {
  x = x + x
}
PRINT x
#2:
n = 1
nsq = 1
100000 LOOP {
  100000 LOOP {
    nsq = nsq + n + n + 1
    n = n + 1
  }
}
PRINT nsq

输出样例

#1:
1024
#2:
4761

样例解释

样例#1中PL/S程序计算了$2^{10}$

样例#2中PL/S程序计算了$(100000*100000+1)^2\mod(10^9+7)$

数据范围

测试点#1~#4，LOOP循环不嵌套
测试点#5~#9，程序中只有一个变量，但LOOP循环可以嵌套
测试点#10~#14，没有特殊限制

4.新挑战*

背景描述

本题不来自USACO月赛

还记得WC 2017第二题挑战吗？这是我的新挑战系列的第二题，第一题在我的创新题目中。

这次，仍然让我们来排序吧，只不过现在排序的是浮点数而已。

题目描述

有n($n\le10^8$)个32位单精度浮点数(C/C++中的float，Pascal中的single)，请在规定的限制下给这些数排序。

输入格式

由于本题输入输出规模非常大，所以使用交互库输入输出。

四个32位整数a,b,x,n。

交互库原型

void init(int a,int b,int x);
float readNext(void);
int writeNext(float x);

procedure init(a,b,x:longint);
function readNext:single;
function writeNext(x:single):longint;

首先调用init(a,b,x)，然后调用n次readNext得到n个浮点数，最后按顺序调用n次writeNext。

注意：请务必在调用完所有readNext后再调用writeNext，否则可能会导致答案错误。

输出格式

一个32位整数，为最后一次调用writeNext函数的返回值。

输入样例

148781241 333135714 547124561 6

输出样例

1282166852

样例解释

6个浮点数分别为5.73938e-018,1.92782e+034,-4.63247e+008,-3.8978e+030,2.16839e-035,-54.5559。

数据范围

测试点编号	n的范围	内存限制	分值
1	$n=200000$	4MB	20
2	$n=2*10^7$	4MB	40
3	$n=10^8$	1GB	40

保证输入数据中没有NaN和-0，但可能有0、inf和-inf。

交互库说明

交互库的名称为specio(special I/O library)。

C/C++选手

找到MinGW安装的位置，设为%mingw。
将specio.h复制到%mingw\%arch\include目录下，其中%arch为编译器的目标体系，如x86_64-w64-mingw32，不同版本目录可能不同。
将libspecio.a(C语言为libcspecio.a)复制到%mingw\%arch\lib目录下。
在程序开头#include<specio.h>。
编译程序时，加上-lspecio选项即可。

Pascal选手

找到Free Pascal安装的位置，设为%fpc。
将specio.o和specio.ppu复制到%fpc\units\i386-win32目录下。
在程序开头加上uses specio;。