CF1477D Nezzar and Hidden Permutations

Nezzar designs a brand new game "Hidden Permutations" and shares it with his best friend, Nanako. At the beginning of the game, Nanako and Nezzar both know integers $ n $ and $ m $ . The game goes in the following way: - Firstly, Nezzar hides two permutations $ p_1,p_2,\ldots,p_n $ and $ q_1,q_2,\ldots,q_n $ of integers from $ 1 $ to $ n $ , and Nanako secretly selects $ m $ unordered pairs $ (l_1,r_1),(l_2,r_2),\ldots,(l_m,r_m) $ ; - After that, Nanako sends his chosen pairs to Nezzar; - On receiving those $ m $ unordered pairs, Nezzar checks if there exists $ 1 \le i \le m $ , such that $ (p_{l_i}-p_{r_i}) $ and $ (q_{l_i}-q_{r_i}) $ have different signs. If so, Nezzar instantly loses the game and gets a score of $ -1 $ . Otherwise, the score Nezzar gets is equal to the number of indices $ 1 \le i \le n $ such that $ p_i \neq q_i $ . However, Nezzar accidentally knows Nanako's unordered pairs and decides to take advantage of them. Please help Nezzar find out two permutations $ p $ and $ q $ such that the score is maximized.

N/A

N/A

For first test case, for each pair given by Nanako: - for the first pair $ (1,2) $ : $ p_1 - p_2 = 1 - 2 = -1 $ , $ q_1 - q_2 = 3 - 4 = -1 $ , they have the same sign; - for the second pair $ (3,4) $ : $ p_3 - p_4 = 3 - 4 = -1 $ , $ q_3 - q_4 = 1 - 2 = -1 $ , they have the same sign. As Nezzar does not lose instantly, Nezzar gains the score of $ 4 $ as $ p_i \neq q_i $ for all $ 1 \leq i \leq 4 $ . Obviously, it is the maximum possible score Nezzar can get.