{"problem":{"name":"『XYGOI round1』一些数","description":{"content":"MX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 $n-1$，MX 有多少种填数方法呢？     Piggy 比较良心。他没有在不同的位置上填相同的数。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9436"},"statements":[{"statement_type":"Markdown","content":"MX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 $n-1$，MX 有多少种填数方法呢？    \n\nPiggy 比较良心。他没有在不同的位置上填相同的数。\n\n## Input\n\n本题有多组测试数据。  \n\n第一行一个整数 $T$ 代表数据组数。  \n对于每组数据：  \n- 第一行两个整数 $n,q$ 代表卡牌个数和 Piggy 已经填上了多少个数。  \n- 第二行 $2q$ 个整数，第 $2i-1,2i$ 个整数 $(x,y)$ 代表第 $x$ 个数被 Piggy 填成了 $y$。\n\n## Output\n\n输出 $T$ 行，每行一个整数代表答案。\n\n[samples]\n\n## Background\n\nMX 在研究排列所具有的性质。这一天，她拿出了 $n$ 张卡片排成一排，想要在上面填数以写成一个 $1\\sim n$ 的排列。  \n\nPiggy 趁 MX 不注意，偷偷在一些卡片上写了数。\n\n## Note\n\n#### 样例解释\n用 $-1$ 代表此位置数字还未确定。  \n样例 $1$：第一组给定的排列为 $-1,2,-1,8,-1,5,6,-1,-1,-1$。容易发现，只有 $1,2,3,8,4,5,6,7,9,10$ 的最长上升子序列长度为 $10-1=9$。第二组给定的排列为 $-1,-1$，$2,1$ 为唯一满足要求的序列。\n\n**本题采用捆绑测试。**\n\n| Subtask | $\\sum n$ | $\\sum q$ |  分值 |\n|:-:|:-:|:-:|:-:|\n|0|$\\le 10$|$\\le 10$|10|\n|1|$\\le 15$|$\\le 10$|20|\n|2|$\\le 5\\times 10^3$|$\\le 5\\times 10^3$|30|\n|3|$\\le 5\\times 10^5$|$\\le 5\\times 10^5$|40| \n\n保证 $ 0\\le q\\le n$，$1\\le n\\le  5\\times 10^5$，$1\\le T\\le 10^5$，$1 \\le x,y \\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9436","tags":["O2优化","洛谷月赛"],"sample_group":[["2\n10 4\n2 2 4 8 6 5 7 6\n2 0","1\n1"],["2\n40 21\n1 1 2 2 6 6 7 7 8 8 9 9 10 10 11 11 15 15 16 16 23 23 24 24 25 25 26 26 30 30 34 35 35 36 36 37 37 38 38 39 40 40\n40 15\n3 3 4 4 14 14 15 15 17 17 19 19 24 23 25 24 27 26 30 29 31 30 33 32 35 34 39 38 40 39","4\n4\n"]],"created_at":"2026-03-03 11:09:25"}}