首先是转化成图论问题：在初始无边的 (20) 个点的有向图 (G_1) 中按某种顺序加边，使得 (forall iin[1,n])，(A_i) 到 (B_i) 有时间递增的路径。
构造 (20) 个点的有向图 (G_2)，(forall iin[1,n])，(A_i) 连向 (B_i)。设弱连通块数为 (c)，DAG 导出子图的最大点数是 (k)。可以构造出一种连 (2n-c-k) 条边的做法：
显然每个弱连通块独立，可以分别考虑。对于 (n) 个点的弱连通块，将点重标号使得最大 DAG 导出子图的拓扑序是 (1,2,cdots,m)，则按顺序连 ((1,2),(2,3),cdots,(m,m+1),(m+1,1)) 和 ((m+1,m+2),cdots,(n-1,n),(n,m+1),cdots,(n-2,n-1))。
然后可以证明 (2n-c-k) 条边是下界。
考虑转化一下命题：设存在一种加 (e) 条边的合法方案，则可以找到一个大小至少为 (2n-c-e) 的点集，其导出子图是 DAG。
证明：增量法维护 (G_2) 的一个点集 (S)。一开始在 (G_1) 中无边，每个弱连通块只有一个点，(S) 是整个点集。然后考虑加一条边 ((u,v))。
- 若 (u,v) 不在同一弱连通块，则合并这两个连通块。此时 (|S|) 不变，弱连通块数 (-1)。
- 若 (u,v) 在同一弱连通块，若 (vin S) 则把 (v) 从 (S) 中删去，否则无事发生。此时弱连通块数不变，(|S|) 至多 (-1)。
可以证明最后得到的 (S) 内的点都不能走回自己，所以是 DAG。且恰好有 (n-c) 条边是第一种情况，因此 (|S|ge n-(e-(n-c))=2n-c-e)，得证。
所以只要把 (c,k) 求出来然后直接输出 (2n-c-k) 就可以所以这 tm 是数竞题么。
计算 DAG 导出子图最大点数可以暴力做状压 dp，对每个点集都计算出它是否是 DAG。时间复杂度 (O(T|Sigma|2^{|Sigma|}+sum n))。