#P17798. [Ontak2024]KAD

[Ontak2024]KAD

题目描述

有 nn 个任务和 nn 名人员,分别编号 11 到 nn。

任务 jj 有两项要求 (pj,kj)(p_j,k_j);人员 ii 有两项能力 (Pi,Ki)(P_i,K_i)。人员 ii 能完成任务 jj,当且仅当

Pi≥pj且Ki≥kj.P_i\ge p_j\quad\text{且}\quad K_i\ge k_j.

每名人员恰好分配一个任务,每个任务恰好分配给一名人员。

请判断合法分配是不存在、恰好一种,还是至少两种。两个方案不同,指至少一名人员分到的任务不同。

输入格式

第一行整数 ss,表示该测试所属的最早子任务编号,1≤s≤71\le s\le7。

第二行整数 nn。

接下来 nn 行,第 jj 行两个整数 pj,kjp_j,k_j,表示任务要求。

再接下来 nn 行,第 ii 行两个整数 Pi,KiP_i,K_i,表示人员能力。

输出格式

输出一行一个整数:

  • 0:不存在合法分配。
  • 1:恰好存在一种合法分配。
  • 2:存在至少两种不同的合法分配。

样例 1

输入:

1
1
1 1
0 0

输出:

0

样例 2

输入:

2
2
0 0
1 1
2 2
3 3

输出:

2

样例 3

输入:

2
3
2 2
0 6
0 0
5 7
5 1
3 5

输出:

1