「MGOI Round 1 B」罪犯

「MGOI Round 1 B」罪犯

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

前奏

真亦是假,假亦是真

题目背景

SY现在是一个法官了,他奉命审理一个复杂的案件

题目描述

现在有\(n\)个嫌疑人,每个都会说一句话,如下:

  • 第\(a_i\)个人说的话是真的/假的

显然由此推出的可能事实不止一种,于是SY想知道共有多少种情况, 最多有多少人是罪犯和最少有多少人是罪犯。

输入格式

第一行有一个正整数 \(n\),表示选项个数。

接下来 \(n\) 行,每行有两个整数 \(a_i\), \(opt_i\),描述一个选项。其中当 \(opt_i\) = 1时,表示这个选项的内容为 第 \(a_i\)个人说的话是真的;当 \(opt_i\) = 0时,表示这个选项的内容为 第 \(a_i\)个人说的话是假的

输出格式

如果没有答案满足这道选择题,输出 No answer。

否则输出三行,每行一个正整数,分别为合法答案数及正确选项最多和最少的答案分别有多少个正确选项。其中正确答案数要对 \(10^9 + 7\)取模。

样例

输入#1

4
2 1
4 0
1 1
2 0

输出#1

2
3
1

数据范围

对于 \(10\%\) 的数据,\(n \leq 10\)。
对于 \(30\%\) 的数据,\(n \leq 100\)。
对于 \(60\%\) 的数据,\(n \leq 10^3\)
对于 \(100\%\) 的数据,\(n\leq 10^6,1\leq a_i\leq n,i\neq a_i,opt_i\in\{0,1\}\)

限制

时间1s,内存256MB

说明

1. 保证题目数据合理

MGOI Round 1

未参加
状态
已结束
规则
ACM/ICPC
题目
3
开始于
2022-06-30 14:00
结束于
2022-07-09 14:00
持续时间
216.0 小时
主持人
参赛人数
22