{"raw_statement":[{"iden":"statement","content":"Carlitos \"Curious\" Nunes is studying the history of China at school. More specifically, he is studying the times known as the \"Golden Age\" of China. The History exam is soon to come and he decided to write some notes to help his studies. He wrote:\n\nThe Golden Age (600–1,600AD) is a period of history when China was ruled by the Tang (618–906AD) and Song (960–1,279AD) dynasties. It is characterized by the end of internal wars and by enormous commercial and technological development (tea, explosives, the compass, and printing).\n\nGrowth in commerce took place during the rule of the Song dynasty. To stimulate the exchange of goods among cities, Emperor Taizu Song built many roads joining the cities of the empire. On the one hand, one could reach any city from any other city using these roads. On the other hand, there were so many roads that people believed the following to hold: for any four cities, say A, B, C, and D,\n\nwhere d(U, V) is the smallest number of roads needed to go from U to V.\n\nThe Golden Age ended when the Mongols invaded China in 1,279AD and established the Yuan dynasty.\n\nGenghis Khan, fearing a Chinese uprising, split the cities of the empire among his army commanders. The split up was performed so that each commander was responsible for a subset of cities such that no two of these cities was joined by a road. Furthermore, each city belonged to precisely one commander.\n\nCarlitos is very curious to find how Genghis Khan could have made such a split, and how many commanders his army should have so that the split was possible. Carlitos wants to solve this puzzle before leaving for his vacation at Foz de Iguaçu. Can you help him?\n\nThe first line has two integers, N and M, the number of cities and roads in the Chinese empire, respectively. The M lines that follow each contain two integers, u and v, the cities joined by one road. There are no two roads joining the same pair of cities.\n\nPrint an integer, the minimum number of commanders required to split up the empire.\n\n"},{"iden":"input","content":"The first line has two integers, N and M, the number of cities and roads in the Chinese empire, respectively. The M lines that follow each contain two integers, u and v, the cities joined by one road. There are no two roads joining the same pair of cities.  1 ≤ N ≤ 5·104  2 ≤ M ≤ 5·105  1 ≤ u, v ≤ N, u ≠ v "},{"iden":"output","content":"Print an integer, the minimum number of commanders required to split up the empire."},{"iden":"examples","content":"Input3 31 21 32 3Output3Input5 41 21 31 41 5Output2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the length of the array.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be a sequence of positive integers.  \n\nA *subarray* of $ A_k $ is a contiguous non-empty subsequence $ A_k[i:j] = (a_{k,i}, a_{k,i+1}, \\dots, a_{k,j}) $ for $ 1 \\leq i \\leq j \\leq n_k $.  \n\nA subarray $ A_k[i:j] $ is a *Super Subarray* if the sum $ S = \\sum_{\\ell=i}^{j} a_{k,\\ell} $ satisfies $ a_{k,\\ell} \\mid S $ for all $ \\ell \\in \\{i, i+1, \\dots, j\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 100 $  \n2. For each test case $ k $:  \n   - $ 1 \\leq n_k \\leq 2000 $  \n   - $ 1 \\leq a_{k,i} \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n_k\\} $  \n\n**Objective**  \nFor each test case $ k $, compute the number of subarrays $ A_k[i:j] $ that are Super Subarrays.","simple_statement":"Count the number of non-empty contiguous subarrays where the sum of elements is divisible by every element in that subarray.","has_page_source":false}