Rhyme
Contest: Kotlin Heroes: Episode 8
Difficulty rating: 1800
Tags: *special, implementation

Let's say that two strings $$$s$$$ and $$$t$$$ rhyme if both strings have length at least $$$k$$$, and their last $$$k$$$ characters are equal. For example, if $$$k = 3$$$, the strings abcd and cebcd rhyme, the strings ab and ab don't rhyme, the strings aaaa and aaaaa rhyme, the strings abcd and abce don't rhyme.

You have $$$n$$$ pairs of strings $$$(s_i, t_i)$$$, and for each pair of strings you know, should they rhyme or should not.

Find all possible non-negative integer values for $$$k$$$ such that pairs that have to rhyme, rhyme and pairs that must not rhyme, don't rhyme.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of string pairs.

Next $$$n$$$ lines contains descriptions of pairs — one per line. The $$$i$$$-th line contains space-separated strings $$$s_i$$$ and $$$t_i$$$ and marker $$$r_i$$$. Strings are non-empty, consist of lowercase Latin letters and each have length at most $$$2 \cdot 10^5$$$. The marker $$$r_i$$$ equals to $$$1$$$ if strings have to rhyme, or $$$0$$$ if they must not rhyme.

It's guaranteed that for each test case there is at least one pair with $$$r_i$$$ equal to $$$1$$$ and that the total length of all strings over all test cases doesn't exceed $$$4 \cdot 10^5$$$.

Output format:
For each test case, firstly print integer $$$m$$$ — the number of possible non-negative integer values of $$$k$$$ such that pairs that have to rhyme, rhyme and pairs that must not rhyme, don't rhyme. Next, print all these values of $$$k$$$ (without repetitions). You can print them in any order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, if $$$k$$$ is at least $$$1$$$ then kotlin and heroes don't rhyme.

In the second test case, for $$$k = 2$$$ join and kotlin rhyme, and episode and eight don't rhyme.

Example input:
3
1
kotlin heroes 1
2
join kotlin 1
episode eight 0
4
abc abcdef 0
xyz zzz 1
aaa bba 0
c d 0

Example output:
1
0
2
1 2
0

Editorial:
Let $$$\mathit{limit}_i$$$ be the maximum value $$$k$$$ such that the $$$i$$$-th pair rhymes regardless of must it or must not. It's easy to calculate $$$\mathit{limit}_i$$$ as the length of the longest equal suffix of $$$s_i$$$ and $$$t_i$$$.
Now, if we know that the $$$i$$$-th pair must rhyme, then any possible $$$k$$$ should not exceed $$$\mathit{limit}_i$$$. But if the $$$i$$$-th pair must not rhyme, then any possible $$$k$$$ should be strictly greater than $$$\mathit{limit}_i$$$.
In other words, all possible $$$k$$$-s form a segment between minimum possible $$$k$$$ and maximum possible $$$k$$$. So, we can calculate minimum possible $$$k$$$ (named $$$l$$$) as $$$\max(\mathit{limit}_i) + 1$$$ among all $$$i$$$ with $$$r_i = 0$$$ and maximum possible $$$k$$$ (named $$$r$$$) as $$$\min(\mathit{limit}_i)$$$ among all $$$i$$$ with $$$r_i = 1$$$.
As a result there will be $$$\max(0, r - l + 1)$$$ possible $$$k$$$ from $$$l$$$ to $$$r$$$.