Do not rape your brain with this problem:), since constraints are really small, - just run straight dynamic, it's look similar to dfs.
After I've corrected some stupid mistakes I've got AC 0.375 124 КБ, without any optimization