{"raw_statement":[{"iden":"statement","content":"One day your university decided to run some statistics. They wanted to study friendship relations among boys and girls, and its effectiveness on their grades.\n\nStrange thing about your university is that it has the exact same number of boys and girls. More formally, the university has P boys numbered from 1 to P, and P girls numbered from 1 to P.\n\nWe know that any pair of boys are surely friends, and any pair of girls are definitely friends. However, boys and girls are not always friends. To be precise, the university has a list of length N containing the friendship relations between girls and boys. the ith friendship relation is described by two integers bi and gi meaning that the boy number bi and girl number gi are friends.\n\nOne of the statistics your university is interested in, is the largest group of people (boys and girls) where any pair of them are friends. Can you write a program that would solve such a problem?\n\nThe first line contains an integer T, the number of test cases.\n\nEach test case starts with a line containing 2 space separated integers P and N denoting both the number of boys and girls at your university, and the number of friendship relations. (1 ≤ P ≤ 20), (0 ≤ N ≤ P2).\n\nN lines follow. The ith line of them contains 2 space separated integers bi, gi describing a friendship relation.\n\nFor each test case print a single line, containing a single integer, denoting the number of people in the largest group where any pair of people among them are friends.\n\n"},{"iden":"input","content":"The first line contains an integer T, the number of test cases.Each test case starts with a line containing 2 space separated integers P and N denoting both the number of boys and girls at your university, and the number of friendship relations. (1 ≤ P ≤ 20), (0 ≤ N ≤ P2).N lines follow. The ith line of them contains 2 space separated integers bi, gi describing a friendship relation."},{"iden":"output","content":"For each test case print a single line, containing a single integer, denoting the number of people in the largest group where any pair of people among them are friends."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of guns.  \nLet $ W \\in \\mathbb{R}^+ $ be the initial weight of Simon.  \nLet $ G = \\{(c_i, r_i) \\mid i \\in \\{1, \\dots, N\\}\\} $ be the set of guns, where:  \n- $ c_i \\in \\mathbb{Z}^+ $ is the cost per unit weight of gun $ i $,  \n- $ r_i \\in [0, 1] $ is the minify ratio of gun $ i $ (weight becomes $ r_i \\cdot \\text{current weight} $).\n\n**Constraints**  \n1. $ 1 \\le N \\le 10^5 $  \n2. $ 1 \\le W \\le 10^4 $  \n3. $ 1 \\le c_i \\le 10^4 $  \n4. $ 0 \\le r_i \\le 1 $\n\n**Objective**  \nMinimize the total cost:  \n$$\n\\min_{\\sigma \\in S_N} \\sum_{i=1}^{N} c_{\\sigma(i)} \\cdot W \\cdot \\prod_{j=1}^{i-1} r_{\\sigma(j)}\n$$  \nwhere $ \\sigma $ is a permutation of $ \\{1, \\dots, N\\} $, representing the order of gun usage.","simple_statement":"Freddy has an elephant named Simon with initial weight W. He has N minifying guns, each can be used only once. Each gun i has a cost coefficient c_i and a reduction ratio r_i (so weight becomes r_i * current weight). The cost of using gun i is c_i multiplied by the current weight of Simon when used. Find the minimum total cost to use all N guns exactly once to shrink Simon.","has_page_source":false}