#P2788. [Poi2012]Festival

    ID: 1896 传统题 1000ms 512MiB 尝试: 598 已通过: 214 难度: 7 上传者: 标签>CF2300提高+/省选-差分约束Tarjan 强连通分量算法缩点Floyd–Warshall负环检测鸣谢oimaster

[Poi2012]Festival

题目描述

有 nn 个正整数 x1…nx_{1\dots n},再给出 m1+m2m_1+m_2 个限制条件,限制分为两类:

  1. 给出 a,ba,b,要求满足 xa+1=xbx_a+1=x_b。
  2. 给出 c,dc,d,要求满足 xc≤xdx_c\leq x_d。

在满足所有限制的条件下,求 x1…nx_{1\dots n} 中最多有多少个不同的值。

输入格式

第一行三个正整数 n,m1,m2n,m_1,m_2。 接下来 m1m_1 行每行两个正整数 a,ba,b,表示第一类限制。 接下来 m2m_2 行每行两个正整数 c,dc,d,表示第二类限制。

输出格式

一个正整数,表示 x1…nx_{1\dots n} 中最多有多少个不同的值。 如果无解输出 NIE。

4 2 2
1 2
3 4
1 4
3 1
3

样例说明

x1=x4=2,x2=3,x3=1x_1=x_4=2,x_2=3,x_3=1,这样答案为 33。 容易发现没有更大的方案。

数据规模与约定

对于 100%100\% 的数据,2≤n≤6002\leq n\leq 600,1≤m1+m2≤1051\leq m_1+m_2\leq 10^5,1≤a,b,c,d≤n1\leq a,b,c,d\leq n。