P21128 [CodeChef] SEGFAULT
提高-
题目描述

There are N people numbered from 1 to N such that:
Exactly one of these people is a thief and always lies;
All the others are honest and always tell the truth.

If the i^{th} person claims that the thief is one person out of $L_{i}, L_{i}+1, L_{i}+2, \cdots, R_{i},$ determine how many people could be the thief.

It is guaranteed that at least one person can be the thief.

------ Input Format ------

  • First line will contain T, the number of test cases. Then the test cases follow.
  • First line of each test case will contain N, the number of people. N lines follow.
  • The i^{th} line contains two space-separated integers - L_{i} and R_{i}, the range of people amongst which the i^{th} person claims the thief is.

------ Output Format ------

  • For each test case, in the first line, output K, the number of possible thieves.
  • In the next K lines, output the list of people that could be the thieves, in ascending order.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$3 ≤ N ≤ 10^{5}$
$1 ≤ L_{i} ≤ R_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $10^{5}$.
- It is guaranteed that at least one person can be the thief.

----- Sample Input 1 ------
1
4
2 2
1 1
1 3
1 3
----- Sample Output 1 ------
2
1
2
----- explanation 1 ------
Test case $1$: Two people (numbered $1$ and $2$) can be thief:
- Person $1$ may be the thief because, the other $3$ people claim that he may be the thief, whereas, he lies and claims that person $2$ is the thief.
- Person $2$ may be the thief because, the other $3$ people claim that he may be the thief, whereas, he lies and claims that person $1$ is the thief.
- Person $3$ cannot be the thief because, he claims that the thief lies in the range $[1, 3]$. If he were the thief, then his statement should be false. However, since 3 lies in $[1, 3]$, his statement would be true, which results in a contradiction. Furthermore, the first $2$ people do not claim that he is the thief. Therefore, he cannot be the thief.
- Person $4$ cannot be the thief because the first $3$ people do not claim that he is the thief.

输入格式

见题面

输出格式

见题面

样例输入
1 4 2 2 1 1 1 3 1 3
样例输出
2 1 2