#GYM104665I. Riddle Me This (Hard Version)
Riddle Me This (Hard Version)
Description
The Mad Hatter has moved past unsolvable riddles, and is now dabbling in unsolvable ciphers. On your recent trip through the looking-glass, he has presented you with a set of $N$ ciphers (which he has no idea how to solve). A cipher of length $s_i$ is a permutation of the integers $1..s_i$.
We consider a cipher solved if it is in ascending order. We can also perform an arbitrary number of rotations on these ciphers, in which we take the last element and move it to the front of the cipher. For example, here is a demonstration of how to solve this cipher:
- Original cipher: $[3, 4, 1, 2]$
- One rotation: $[2, 3, 4, 1]$
- Two rotations: $[1, 2, 3, 4]$, which is now in ascending order, so this cipher is solved.
However, these looking-glass ciphers have a special property: each cipher is entangled with another cipher, such that rotations performed on the first cipher will automatically be applied to the other cipher! Luckily, you've brought your looking-glass snare wand, which allows you to choose how to entangle the ciphers. Specifically, every cipher must be entangled with exactly one other cipher.
After you have entangled all ciphers, you will proceed to solve as many ciphers as you can by performing rotations on each pair of entangled ciphers. How many ciphers can you solve, if you entangle the ciphers optimally?
This is the hard version of this problem. The only difference between the two versions are the constraints on the input. In this version, $N \le 100$, and there are no restrictions on each $s_i$, except that $1 \le s_i \le 10^3$).
The first line of input will contain a single integer $N$ denoting the number of ciphers. It is guaranteed that $N$ is even. ($2 \le N \le 100$)
The next $N$ lines represent the ciphers, permutations of length $s_1,...,s_N$. ($1 \le s_i \le 10^3$) Each line contains $s_i$ (the length of the permutation), followed by the permutation itself.
Output a single integer, the number of ciphers you can solve if you provide an optimal initial entanglement.
Input
The first line of input will contain a single integer $N$ denoting the number of ciphers. It is guaranteed that $N$ is even. ($2 \le N \le 100$)
The next $N$ lines represent the ciphers, permutations of length $s_1,...,s_N$. ($1 \le s_i \le 10^3$) Each line contains $s_i$ (the length of the permutation), followed by the permutation itself.
Output
Output a single integer, the number of ciphers you can solve if you provide an optimal initial entanglement.
4
4 1 4 2 3
4 3 4 1 2
4 2 3 4 1
4 2 3 4 1
4
6 1 2 5 6 4 3
6 6 1 2 3 4 5
8 5 6 7 8 1 2 3 4
4 1 2 3 4
3
3