{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eДан ориентированный ациклический граф\u0026nbsp;\u003cimg class\u003d\"tex\" src\u003d\"http://e-maxx.ru/tex2png/cache/4c5f3ba22ad1fd775e82380ae681dbdb.png\" alt\u003d\"G\" /\u003e. Требуется покрыть его наименьшим числом путей, т.е. найти наименьшее по мощности множество непересекающихся по вершинам простых путей, таких, что каждая вершина принадлежит какому-либо пути.\u003c/p\u003e\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eНа первой строке записана количество тестов \u003cem\u003eT\u003c/em\u003e\u0026nbsp;(\u003cspan class\u003d\"tex-span\"\u003e0\u0026thinsp;\u0026le;\u0026thinsp;\u003cem\u003eT\u003c/em\u003e\u0026thinsp;\u0026le;\u0026thinsp;100\u003c/span\u003e).\u003c/p\u003e\n\u003cp\u003eКаждый тест начинается с пустой строки. Следующая строка содержит два целых числа\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003cem\u003en\u003c/em\u003e\u003c/span\u003e\u0026nbsp;и\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003cem\u003em\u003c/em\u003e\u003c/span\u003e\u0026nbsp;(\u003cspan class\u003d\"tex-span\"\u003e1\u0026thinsp;\u0026le;\u0026thinsp;\u003cem\u003en\u003c/em\u003e\u0026thinsp;\u0026le;\u0026thinsp;1000, 0\u0026nbsp;\u0026le; m\u0026nbsp;\u0026le; 10000\u003c/span\u003e).\u003c/p\u003e\n\u003cp\u003eСледующие\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003cem\u003em\u003c/em\u003e\u003c/span\u003e\u0026nbsp;строк содержат ребра. Каждая строка содержит два целых числа\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003cem\u003ev\u003c/em\u003e\u003c/span\u003e,\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003cem\u003eu\u003c/em\u003e\u003c/span\u003e\u0026nbsp;(\u003cspan class\u003d\"tex-span\"\u003e1\u0026thinsp;\u0026le;\u0026thinsp;\u003cem\u003ev\u003c/em\u003e,\u0026thinsp;\u003cem\u003eu\u003c/em\u003e\u0026thinsp;\u0026le;\u0026thinsp;\u003cem\u003en\u003c/em\u003e\u003c/span\u003e,\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003cem\u003ev\u003c/em\u003e\u0026thinsp;\u0026ne;\u0026thinsp;\u003cem\u003eu\u003c/em\u003e\u003c/span\u003e), которые означают, что есть ребро из вершины\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003cem\u003ev\u003c/em\u003e\u003c/span\u003e\u0026nbsp;в\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003cem\u003eu\u003c/em\u003e\u003c/span\u003e. Между каждой парой вершин есть не более одного ребра. Гарантируется, что в графе нет циклов.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e Для каждого теста выведите ответ \u003c/p\u003e\n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e4 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3 4\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 2\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e5 4\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 2\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3 2\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 4\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 5\u003c/span\u003e\u003c/p\u003e "}},{"title":"Sample Output","value":{"format":"HTML","content":" \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 1: 2\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 2: 1\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 3: 3\u003c/span\u003e\u003c/p\u003e "}}]}