{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eAlice and Bob are playing a card game. In this card game, a number is written on each face of the playing card. The rule of the game is described as follows:\u003cbr\u003e\u003cbr\u003e- Alice arranges the cards in a row, and for each of the cards, she chooses one of its faces to place it up;\u003cbr\u003e- Bob turns over minimum number of cards to make all numbers on the front faces unique.\u003cbr\u003e\u003cbr\u003eThey play the game some times, and Bob always succeeds making the numbers unique. However, both of them are not sure whether the number of cards flipped is minimum. Moreover, they want to figure out the number of different ways of turning over minimum number of cards to make the numbers unique. Two ways are considered equal if and only if the sets of flipped cards are equal. Please write a program to help them!\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input is a single integer $T$ $(1 \\leq T \\leq 50)$, the number of test cases.\u003cbr\u003e\u003cbr\u003eEach test case begins with a single line of integer $n$ $(1 \\leq n \\leq 10^5)$, the number of cards on the table. Then follow $n$ lines, specifying the cards that Alice arranges. Each of these $n$ lines contains two integers $x, y$ $(1 \\leq x, y \\leq 2n)$, meaning that Alice places a card with number $x$ on the front face and number $y$ on the back face.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, display two integers in a line, the minimum number of cards to turn over, and the number of different ways of flipping modulo $998244353$, respectively. If it is impossible to turn over cards to make all numbers unique, display $\\texttt{-1 -1}$ instead."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n4\r\n1 2\r\n1 3\r\n4 5\r\n4 6\r\n2\r\n1 1\r\n1 1\r\n3\r\n1 2\r\n3 4\r\n5 6\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 4\r\n-1 -1\r\n0 1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn the first sample test case, Bob may turn over one of the first two cards and one of the last two cards, so there are four different ways of turning over two cards to\u003cbr\u003emake all numbers on the front faces unique. Obviously, this can\u0027t be done with less than two cards flipped.\u003cbr\u003e\u003cbr\u003eIn the second sample test case, it is impossible to make all numbers on the front faces unique.\u003cbr\u003e\u003cbr\u003eIn the third sample test case, all numbers on the front faces are already distinct.\u003cbr\u003e"}}]}