• check all unit segments; if there's one covered by 0 or 1 intervals, the answer is trivially "impossible"; for each of them covered by exactly 2 intervals, we know they must have different directions
• there's always a covering with at most 3 intervals covering each unit segment — let's take the largest interval, then while we're not done: choose the interval that starts in the currently covered part and extends it as much as possible (proof is left to the reader, it's pretty simple)
• in fact, this covering has at most 2 intervals per unit segment, except possibly some covered by the first, second and last of the intervals chosen by the above algorithm
• let's use the precomputed rules for pairs with different directions: in each step except the last, we can always choose the next interval to add to our covering in such a way that none of these rules will be broken (proof again left to the reader), so if we use these rules, we can only fail on the intersection of the first and last added interval
• let's use these rules again: immediately after we know the first interval, we can precompute (by BFS, the rules must form a bipartite graph or the answer is impossible) which intervals can't be in our covering; if we make sure to never consider adding these intervals to our covering, then no rules can be broken
• this way, we built one covering and it never uses all intervals covering some unit segment, so its complement is also a valid covering

However, what I didn't handle is that we still need to ensure there won't be 3 intervals (1st, 2nd, last) covering some unit segment. Of course, if there are multiple choices of the last interval to add, then we can choose the one with minimal overlap with the 1st interval, so there will be another interval that's not in our covering and each segment in the overlap of the 1st and last interval is also covered by this interval (which is not in the covering, so it's in the opposite direction). The other case, when there's only one choice for the last segment, is harder and I don't know how to easily extend this solution to accomodate it. Any ideas? It turns out we can just add that last interval normally and remove the first interval from our covering without breaking it.

To be precise, my solution gives covering of [1..13] with ([1..10], [3..11], [12..3]) and ([1], [2], [4]..[13]), which isn't valid, but there's a valid covering with ([1..10], [3..11], [12], [13]) and ([12..3], [4]..[11]).

This isn't even a solution made to pass the real tests, I just implemented what I thought was correct and missed the fact that having 3 intervals covering something is possible at the end...