[Solution] Rhyme solution codeforces | Kotlin Heroes: Episode 8

Rhyme solution codeforces


Let’s say that two strings ss and tt rhyme if both strings have length at least kk, and their last kk characters are equal. For example, if k=3k=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 nn pairs of strings (si,ti)(si,ti), and for each pair of strings you know, should they rhyme or should not.

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

Rhyme solution codeforces

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t10001≤t≤1000). Description of the test cases follows.

The first line of each test case contains a single integer nn (1n1051≤n≤105) — the number of string pairs.

Next nn lines contains descriptions of pairs — one per line. The ii-th line contains space-separated strings sisi and titi and marker riri. Strings are non-empty, consist of lowercase Latin letters and each have length at most 21052⋅105. The marker riri equals to 11 if strings have to rhyme, or 00 if they must not rhyme.

It’s guaranteed that for each test case there is at least one pair with riri equal to 11 and that the total length of all strings over all test cases doesn’t exceed 41054⋅105.

Rhyme solution codeforces

Output

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

Rhyme solution codeforces

Example
input

Copy
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

Rhyme solution codeforces

output

Copy
1
0
2
1 2
0

Rhyme solution codeforces

Note

In the first test case, if kk is at least 11 then kotlin and heroes don’t rhyme.

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



Rhyme solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment