Shopee Code League 2022 Qualification Round has just finished, but I'm stucked on a problem called "Connecting the Numbers".

Problem is simple, given 1~n with each number appear twice on a circle (2n numbers in the circle), we can connect the same number inside the circle or outside the circle. We need to check whether or not we can connect all the n pair of numbers without any cross.

2 <= n <= 1e5, 2*n numbers in the input and each number is within [1, n]

I think it's 2-sat, but wa on test3 and MLE on test 5. Do you have any other solutions?