C. Dependency management

problem_index: C

time_limit: 4 seconds

memory_limit: 256 megabytes

note:
The first sample is given in the pic below. Arrow from A to B means that B directly depends on A. Projects that Polycarp's project «a» (version 3) depends on are painted black.
![image](images/cf_928_C/1.png)
The second sample is again given in the pic below. Arrow from A to B means that B directly depends on A. Projects that Polycarp's project «codehorses» (version 5) depends on are paint it black. Note that «extra 1» is chosen instead of «extra 3» since «mashadb 1» and all of its dependencies are ignored due to «mashadb 2».
![image](images/cf_928_C/2.png)

input_output: {"inputs": ["4\na 3\n2\nb 1\nc 1\n\nb 2\n0\n\nb 1\n1\nb 2\n\nc 1\n1\nb 2\n", "9\ncodehorses 5\n3\nwebfrmk 6\nmashadb 1\nmashadb 2\n\ncommons 2\n0\n\nmashadb 3\n0\n\nwebfrmk 6\n2\nmashadb 3\ncommons 2\n\nextra 4\n1\nextra 3\n\nextra 3\n0\n\nextra 1\n0\n\nmashadb 1\n1\nextra 3\n\nmashadb 2\n1\nextra 1\n", "3\nabc 1\n2\nabc 3\ncba 2\n\nabc 3\n0\n\ncba 2\n0\n", "1\nabc 1000000\n0\n", "3\nppdpd 283157\n1\npddpdpp 424025\n\nppdpd 529292\n1\nppdpd 283157\n\npddpdpp 424025\n0\n", "5\nabbzzz 646068\n0\n\nzabza 468048\n2\nbb 902619\nzabza 550912\n\nzabza 217401\n2\nabbzzz 646068\nbb 902619\n\nzabza 550912\n1\nzabza 217401\n\nbb 902619\n1\nabbzzz 646068\n", "5\nyyyy 223967\n1\nyyyyyyy 254197\n\nyyyyyyy 254197\n0\n\ny 442213\n0\n\ny 965022\n1\nyyyyyyy 254197\n\nyyyy 766922\n4\nyyyyyyy 254197\ny 442213\nyyyy 223967\ny 965022\n", "3\nvvgvvgv 991444\n1\ngvgvgvgvgg 206648\n\nvvgvvgv 296188\n0\n\ngvgvgvgvgg 206648\n1\nvvgvvgv 296188\n", "5\ntctocototo 984516\n1\ncttocottt 486791\n\ntctocototo 688522\n2\ncttocottt 486791\ntctocototo 984516\n\ncttocottt 486791\n0\n\ntctocototo 676435\n1\ntctocototo 394244\n\ntctocototo 394244\n2\ntctocototo 688522\ncttocottt 486791\n", "5\nggggggggg 202537\n4\ngggggggg 868552\ngggg 234633\ngggg 402994\ngggggggg 86863\n\ngggg 402994\n0\n\ngggggggg 868552\n1\ngggg 234633\n\ngggg 234633\n1\ngggg 402994\n\ngggggggg 86863\n0\n", "4\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n0\n\ndb 1\n1\nold 1\n\nold 1\n0\n", "5\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n1\nold 1\n\ndb 1\n1\nold 2\n\nold 1\n0\n\nold 2\n0\n", "5\ntctocototo 984516\n1\ncttocottt 486791\n\ntctocototo 688522\n2\ncttocottt 486791\ntctocototo 984516\n\ncttocottt 486791\n0\n\ntctocototo 676435\n1\ntctocototo 394244\n\ntctocototo 394244\n2\ntctocototo 688522\ncttocottt 486791\n", "3\nvvgvvgv 991444\n1\ngvgvgvgvgg 206648\n\nvvgvvgv 296188\n0\n\ngvgvgvgvgg 206648\n1\nvvgvvgv 296188\n", "5\nggggggggg 202537\n4\ngggggggg 868552\ngggg 234633\ngggg 402994\ngggggggg 86863\n\ngggg 402994\n0\n\ngggggggg 868552\n1\ngggg 234633\n\ngggg 234633\n1\ngggg 402994\n\ngggggggg 86863\n0\n", "5\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n1\nold 1\n\ndb 1\n1\nold 2\n\nold 1\n0\n\nold 2\n0\n", "4\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n0\n\ndb 1\n1\nold 1\n\nold 1\n0\n", "1\nabc 1000000\n0\n", "5\nyyyy 223967\n1\nyyyyyyy 254197\n\nyyyyyyy 254197\n0\n\ny 442213\n0\n\ny 965022\n1\nyyyyyyy 254197\n\nyyyy 766922\n4\nyyyyyyy 254197\ny 442213\nyyyy 223967\ny 965022\n", "5\nabbzzz 646068\n0\n\nzabza 468048\n2\nbb 902619\nzabza 550912\n\nzabza 217401\n2\nabbzzz 646068\nbb 902619\n\nzabza 550912\n1\nzabza 217401\n\nbb 902619\n1\nabbzzz 646068\n", "3\nppdpd 283157\n1\npddpdpp 424025\n\nppdpd 529292\n1\nppdpd 283157\n\npddpdpp 424025\n0\n", "5\ntctocototo 984516\n1\ncttocottt 450419\n\ntctocototo 688522\n2\ncttocottt 486791\ntctocototo 984516\n\ncttocottt 486791\n0\n\ntctocototo 676435\n1\ntctocototo 394244\n\ntctocototo 394244\n2\ntctocototo 688522\ncttocottt 486791\n", "3\nvvgvvgv 991444\n1\ngvgvgvgvgg 206648\n\nvgvvgvv 296188\n0\n\ngvgvgvgvgg 206648\n1\nvvgvvgv 296188\n", "5\nggggggggg 202537\n4\ngggggggg 868552\ngggg 234633\ngggg 402994\nggggggfg 86863\n\ngggg 402994\n0\n\ngggggggg 868552\n1\ngggg 234633\n\ngggg 234633\n1\ngggg 402994\n\ngggggggg 86863\n0\n", "5\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n1\nold 1\n\ndb 1\n1\nold 2\n\nold 1\n0\n\nold 3\n0\n", "4\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n0\n\ndb 1\n1\nole 1\n\nold 1\n0\n", "5\nyyyy 223967\n1\nyyyyyyy 254197\n\nyyyyyyy 254197\n0\n\ny 442213\n0\n\ny 965022\n1\nyyyyyyy 254197\n\nyyyy 766922\n4\nyyyyyyy 254197\ny 442213\nyyyy 82207\ny 965022\n", "5\nabbzzz 646068\n0\n\nzabza 468048\n2\nbb 902619\nazbaz 550912\n\nzabza 217401\n2\nabbzzz 646068\nbb 902619\n\nzabza 550912\n1\nzabza 217401\n\nbb 902619\n1\nabbzzz 646068\n", "3\nppdpd 283157\n1\npddpdpq 424025\n\nppdpd 529292\n1\nppdpd 283157\n\npddpdpp 424025\n0\n", "3\nabc 1\n2\nabc 3\ncba 2\n\nabd 3\n0\n\ncba 2\n0\n", "9\ncodehorses 5\n3\nwebfrmk 6\nmashadb 1\nmashadb 2\n\u00a0\ncommons 2\n0\n\u00a0\nlashadb 3\n0\n\u00a0\nwebfrmk 6\n2\nmashadb 3\ncommons 2\n\u00a0\nextra 4\n1\nextra 3\n\u00a0\nextra 3\n0\n\u00a0\nextra 1\n0\n\u00a0\nmashadb 1\n1\nextra 3\n\u00a0\nmashadb 2\n1\nextra 1\n", "4\na 3\n2\nb 1\nc 1\n\u00a0\nb 2\n0\n\u00a0\nb 1\n1\nb 2\n\u00a0\nc 1\n0\nb 2\n", "5\nggggggggg 202537\n4\ngggggggg 868552\ngggg 234633\ngggg 452870\nggggggfg 86863\n\ngggg 402994\n0\n\ngggggggg 868552\n1\ngggg 234633\n\ngggg 234633\n1\ngggg 402994\n\ngggggggg 86863\n0\n", "5\nabbzzz 646068\n1\n\nzabza 468048\n2\nbb 902619\nazbaz 550912\n\nzabza 217401\n2\nabbzzz 646068\nbb 902619\n\nzabza 550912\n1\nzabza 217401\n\nbb 902619\n1\nabbzzz 646068\n", "3\nppdpd 283157\n1\npddppdq 424025\n\nppdpd 529292\n1\nppdpd 283157\n\npddpdpp 424025\n0\n", "5\nggggggggg 202537\n4\ngggggggg 868552\ngggg 234633\nfggg 452870\nggggggfg 86863\n\ngggg 402994\n0\n\ngggggggg 868552\n1\ngggg 234633\n\ngggg 234633\n1\ngggg 402994\n\ngggggggg 86863\n0\n", "4\ncf 1\n1\ndb 1\ndb 2\n\ndb 2\n0\n\ndb 1\n1\nole 1\n\ndlo 1\n0\n", "4\na 3\n2\na 1\nc 1\n\u00a0\nb 2\n0\n\u00a0\nb 1\n1\nb 2\n\u00a0\nc 1\n0\na 2\n", "5\ntctocototo 984516\n1\ncttocottt 450419\n\ntctocototo 688522\n2\ncttocottt 486791\ntctocototo 984516\n\ndttocottt 486791\n0\n\ntctocototo 676435\n1\ntctocototo 394244\n\ntctocototo 394244\n2\ntctocototo 688522\ncttocottt 486791\n", "5\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n1\nold 1\n\ndb 1\n2\nold 2\n\nold 1\n0\n\nold 3\n0\n", "4\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n0\n\ndb 1\n1\nole 1\n\ndlo 1\n0\n", "5\nyyyy 223967\n1\nyyyyyyy 254197\n\nyyyyyzy 254197\n0\n\ny 442213\n0\n\ny 965022\n1\nyyyyyyy 254197\n\nyyyy 766922\n4\nyyyyyyy 254197\ny 442213\nyyyy 82207\ny 965022\n", "9\ncodehorses 5\n3\nwebfrmk 6\nmashadb 1\nmashadb 2\n\u00a0\ncommons 2\n0\n\u00a0\nlashadb 3\n0\n\u00a0\nwebfrmk 6\n2\nmashadb 3\ncommons 2\n\u00a0\nextra 4\n1\nextra 3\n\u00a0\nextra 3\n0\n\u00a0\nextra 1\n0\n\u00a0\nmashadb 1\n1\nextra 3\n\u00a0\nmashadb 2\n1\nartxe 1\n", "4\na 3\n2\nb 1\nc 1\n\u00a0\nb 2\n0\n\u00a0\nb 1\n1\nb 2\n\u00a0\nc 1\n0\na 2\n", "5\ntctocototo 984516\n1\ncttocottt 450419\n\ntctocototo 621283\n2\ncttocottt 486791\ntctocototo 984516\n\ndttocottt 486791\n0\n\ntctocototo 676435\n1\ntctocototo 394244\n\ntctocototo 394244\n2\ntctocototo 688522\ncttocottt 486791\n", "5\ncf 1\n2\ndb 1\ndb 2\n\ndb 2\n1\nold 1\n\ndb 1\n2\nold 2\n\nold 1\n0\n\nold 4\n0\n", "5\nyyyy 223967\n1\nyyyyyyy 254197\n\nyyyyyzy 254197\n0\n\ny 442213\n0\n\ny 1644738\n1\nyyyyyyy 254197\n\nyyyy 766922\n4\nyyyyyyy 254197\ny 442213\nyyyy 82207\ny 965022\n", "5\nabbzzz 646068\n1\n\nzabza 468048\n3\nbb 902619\nazbaz 550912\n\nzabza 217401\n2\nabbzzz 646068\nbb 902619\n\nzabza 550912\n1\nzabza 217401\n\nbb 902619\n1\nabbzzz 646068\n", "3\nppepd 283157\n1\npddppdq 424025\n\nppdpd 529292\n1\nppdpd 283157\n\npddpdpp 424025\n0\n", "9\ncodehorses 5\n3\nwebfrmk 6\nmashadb 1\nmashadb 2\n\u00a0\ncommons 2\n0\n\u00a0\nlashadb 3\n0\n\u00a0\nwebfrmk 6\n2\nmashadb 3\ncommons 2\n\u00a0\nextra 4\n1\nextra 3\n\u00a0\nextra 3\n0\n\u00a0\nextra 1\n1\n\u00a0\nmashadb 1\n1\nextra 3\n\u00a0\nmashadb 2\n1\nartxe 1\n", "5\ntctocototo 984516\n1\ncttocottt 450419\n\ntctocototo 621283\n2\nctuocottt 486791\ntctocototo 984516\n\ndttocottt 486791\n0\n\ntctocototo 676435\n1\ntctocototo 394244\n\ntctocototo 394244\n2\ntctocototo 688522\ncttocottt 486791\n", "5\nggggggggg 202537\n4\ngggggggg 868552\ngggg 234633\nfggg 452870\nggggggfg 86863\n\ngggg 402994\n0\n\ngggggggg 868552\n1\ngggg 234633\n\ngggg 234633\n1\ngggg 617435\n\ngggggggg 86863\n0\n", "5\ncf 1\n0\ndb 1\ndb 2\n\ndb 2\n1\nold 1\n\ndb 1\n2\nold 2\n\nold 1\n0\n\nold 4\n0\n", "4\ncf 1\n1\ndb 1\ndb 3\n\ndb 2\n0\n\ndb 1\n1\nole 1\n\ndlo 1\n0\n", "5\nyyyy 223967\n1\nyyyyyyy 254197\n\nyyyxyzy 254197\n0\n\ny 442213\n0\n\ny 1644738\n1\nyyyyyyy 254197\n\nyyyy 766922\n4\nyyyyyyy 254197\ny 442213\nyyyy 82207\ny 965022\n", "5\nabbzzz 646068\n1\n\nzabza 468048\n3\nbb 902619\nazb`z 550912\n\nzabza 217401\n2\nabbzzz 646068\nbb 902619\n\nzabza 550912\n1\nzabza 217401\n\nbb 902619\n1\nabbzzz 646068\n", "3\nppepd 283157\n1\npddppdq 424025\n\nppdpd 529292\n1\nppdpd 266499\n\npddpdpp 424025\n0\n", "9\ncodehorses 5\n3\nwebfrmk 6\nmashadb 1\nmashadb 2\n\u00a0\ncommont 2\n0\n\u00a0\nlashadb 3\n0\n\u00a0\nwebfrmk 6\n2\nmashadb 3\ncommons 2\n\u00a0\nextra 4\n1\nextra 3\n\u00a0\nextra 3\n0\n\u00a0\nextra 1\n1\n\u00a0\nmashadb 1\n1\nextra 3\n\u00a0\nmashadb 2\n1\nartxe 1\n", "4\na 3\n0\na 1\nc 1\n\u00a0\nb 2\n0\n\u00a0\nb 1\n1\nb 2\n\u00a0\nc 1\n0\na 2\n", "5\ntctocototo 984516\n2\ncttocottt 450419\n\ntctocototo 621283\n2\nctuocottt 486791\ntctocototo 984516\n\ndttocottt 486791\n0\n\ntctocototo 676435\n1\ntctocototo 394244\n\ntctocototo 394244\n2\ntctocototo 688522\ncttocottt 486791\n", "5\nggggggggg 202537\n4\ngggggggg 868552\ngggg 234633\nfggg 452870\nggggggfg 86863\n\ngggg 402994\n0\n\ngggggggg 868552\n1\ngggg 234633\n\ngggg 234633\n2\ngggg 617435\n\ngggggggg 86863\n0\n", "5\ncf 1\n0\ndb 1\ndb 2\n\ndb 2\n0\nold 1\n\ndb 1\n2\nold 2\n\nold 1\n0\n\nold 4\n0\n", "4\ncf 1\n1\ndb 1\ndb 3\n\ndb 2\n0\n\nbd 1\n1\nole 1\n\ndlo 1\n0\n", "5\nyyyy 223967\n1\nyyyyyyy 254197\n\nyyyxyzy 254197\n0\n\ny 442213\n0\n\ny 1644738\n1\nyyyyyyy 254197\n\nyyyy 766922\n4\nyyyyyyy 254197\ny 442213\nyyyy 99568\ny 965022\n", "5\nabbzzz 646068\n1\n\nzabza 468048\n3\nbb 902619\nazb`z 550912\n\nazbaz 217401\n2\nabbzzz 646068\nbb 902619\n\nzabza 550912\n1\nzabza 217401\n\nbb 902619\n1\nabbzzz 646068\n", "3\nabc 1\n2\nabc 3\ncba 2\n\nabc 3\n0\n\ncba 2\n0\n", "9\ncodehorses 5\n3\nwebfrmk 6\nmashadb 1\nmashadb 2\n\u00a0\ncommons 2\n0\n\u00a0\nmashadb 3\n0\n\u00a0\nwebfrmk 6\n2\nmashadb 3\ncommons 2\n\u00a0\nextra 4\n1\nextra 3\n\u00a0\nextra 3\n0\n\u00a0\nextra 1\n0\n\u00a0\nmashadb 1\n1\nextra 3\n\u00a0\nmashadb 2\n1\nextra 1\n", "4\na 3\n2\nb 1\nc 1\n\u00a0\nb 2\n0\n\u00a0\nb 1\n1\nb 2\n\u00a0\nc 1\n1\nb 2\n"], "outputs": ["2\nb 1\nc 1\n", "4\ncommons 2\nextra 1\nmashadb 2\nwebfrmk 6\n", "1\ncba 2\n", "0\n", "1\npddpdpp 424025\n", "0\n", "1\nyyyyyyy 254197\n", "1\ngvgvgvgvgg 206648\n", "1\ncttocottt 486791\n", "2\ngggg 402994\ngggggggg 868552\n", "1\ndb 2\n", "2\ndb 2\nold 1\n", "1\ncttocottt 486791\n", "1\ngvgvgvgvgg 206648\n", "2\ngggg 402994\ngggggggg 868552\n", "2\ndb 2\nold 1\n", "1\ndb 2\n", "0\n", "1\nyyyyyyy 254197\n", "0\n", "1\npddpdpp 424025\n", "1\ncttocottt 450419\n", "1\ngvgvgvgvgg 206648\n", "3\ngggg 402994\nggggggfg 86863\ngggggggg 868552\n", "2\ndb 2\nold 1\n", "1\ndb 2\n", "1\nyyyyyyy 254197\n", "0\n", "1\npddpdpq 424025\n", "1\ncba 2\n", "2\nmashadb 2\nwebfrmk 6\n", "2\nb 1\nc 1\n", "3\ngggg 452870\nggggggfg 86863\ngggggggg 868552\n", "1\nzabza 468048\n", "1\npddppdq 424025\n", "4\nfggg 452870\ngggg 234633\nggggggfg 86863\ngggggggg 868552\n", "1\ndb 1\n", "1\nc 1\n", "1\ncttocottt 450419\n", "2\ndb 2\nold 1\n", "1\ndb 2\n", "1\nyyyyyyy 254197\n", "2\nmashadb 2\nwebfrmk 6\n", "2\nb 1\nc 1\n", "1\ncttocottt 450419\n", "2\ndb 2\nold 1\n", "1\nyyyyyyy 254197\n", "1\nzabza 468048\n", "1\npddppdq 424025\n", "2\nmashadb 2\nwebfrmk 6\n", "1\ncttocottt 450419\n", "4\nfggg 452870\ngggg 234633\nggggggfg 86863\ngggggggg 868552\n", "0\n", "1\ndb 1\n", "1\nyyyyyyy 254197\n", "1\nzabza 468048\n", "1\npddppdq 424025\n", "2\nmashadb 2\nwebfrmk 6\n", "0\n", "1\ncttocottt 450419\n", "4\nfggg 452870\ngggg 234633\nggggggfg 86863\ngggggggg 868552\n", "0\n", "1\ndb 1\n", "1\nyyyyyyy 254197\n", "1\nzabza 468048\n", "1\ncba 2\n", "2\nmashadb 2\nwebfrmk 6\n", "2\nb 1\nc 1\n"]}

solutions: ["n = int(input())\nnames_set = set()\ns = {}\nnames = []\narr = [[] for j in range(n)]\ng = 0\nfor i in range(n):\n\tel = input()\n\tnames_set.add(el.split()[0])\n\tind = 0\n\tif s.get(el) is None:\n\t\ts[el] = g\n\t\tnames.append(el)\n\t\tg += 1\n\tk = int(input())\n\tfor j in range(k):\n\t\tel2 = input()\n\t\tif s.get(el2) is None:\n\t\t\ts[el2] = g\n\t\t\tnames.append(el2)\n\t\t\tg += 1\n\t\tarr[s.get(el)].append(s.get(el2))\n\tif i != n - 1:\n\t\tr = input()\nres = []\nq = []\nq.append(0)\nsp = {}\nwhile len(q):\n\tel = q[0]\n\tdel q[0]\n\t(name, vers) = names[el].split()\n\tif name in names_set:\n\t\ttry:\n\t\t\tsp[name] = max(int(vers), sp[name])\n\t\texcept:\n\t\t\tsp[name] = int(vers)\n\tif not len(q):\n\t\tfor i in sp:\n\t\t\tnames_set.remove(i)\n\t\t\tnew_el = []\n\t\t\tnew_el.append(i)\n\t\t\tnew_el.append(sp[i])\n\t\t\tres.append(new_el[:])\n\t\t\tind = s[str(new_el[0]) + ' ' + str(new_el[1])]\n\t\t\tfor j in range(len(arr[ind])):\n\t\t\t\tp = arr[ind][j]\n\t\t\t\tq.append(p)\n\t\tsp = {}\nres = res[1:]\nres.sort()\nprint(len(res))\nfor i in res:\n\tprint(i[0], i[1])\n", "def scan_project():\n\t(name, version_str) = input().split()\n\treturn (name, int(version_str))\nn = int(input())\n(projects, depends) = ([], {})\nfor i in range(n):\n\tif i > 0:\n\t\tinput()\n\tproject = scan_project()\n\tprojects.append(project)\n\tdepends[project] = [scan_project() for j in range(int(input()))]\n(root_name, root_version) = projects[0]\nlevel_depends = [projects[0]]\nall_depends = {root_name: root_version}\nwhile level_depends:\n\tlevel_depends = list(set(((name, version) for project in level_depends for (name, version) in depends[project] if name not in all_depends)))\n\tfor (name, version) in sorted(level_depends):\n\t\tall_depends[name] = version\n\tlevel_depends = [(name, version) for (name, version) in level_depends if all_depends[name] == version]\nall_depends.pop(root_name)\nprint(len(all_depends))\nfor name in sorted(all_depends):\n\tprint(name, all_depends[name])\n", "from collections import defaultdict\n\ndef rp():\n\ts = input().split()\n\treturn (s[0], int(s[1]))\nps = {}\nn = int(input())\nfor i in range(n):\n\tp = rp()\n\td = []\n\tfor _ in range(int(input())):\n\t\td += [rp()]\n\tps[p] = d\n\tif i != n - 1:\n\t\tinput()\nroot = list(ps.keys())[0]\nq = [(root, 0)]\nu = {root[0]: (root[1], 0)}\nfor (i, l) in q:\n\tisp = i\n\tif isp[0] in u and isp[1] != u[isp[0]][0]:\n\t\tcontinue\n\tfor p in ps[i]:\n\t\tpsp = p\n\t\tif psp[0] not in u or (u[psp[0]][1] == l + 1 and u[psp[0]][0] < psp[1]):\n\t\t\tu[psp[0]] = (psp[1], l + 1)\n\t\t\tq.append((psp, l + 1))\ndel u[root[0]]\nprint(len(u))\nfor i in sorted(u):\n\tprint(i, u[i][0])\n", "levels = []\nconnect = dict()\nn = int(input())\nk = input().split()\nlevels.append({k[0]: int(k[1])})\nconnect[k[0] + ' ' + str(k[1])] = []\nd = int(input())\nfor i in range(d):\n\tconnect[k[0] + ' ' + str(k[1])].append(input())\nfor i in range(n - 1):\n\ts = input()\n\ts = input()\n\tconnect[s] = []\n\tk = int(input())\n\tfor j in range(k):\n\t\tconnect[s].append(input())\nlev = 0\nwhile len(levels[len(levels) - 2]):\n\tlevels.append(dict())\n\tfor projname in levels[lev]:\n\t\tlisting = connect[projname + ' ' + str(levels[lev][projname])]\n\t\tfor i in listing:\n\t\t\tname = i.split()\n\t\t\tgov = True\n\t\t\tfor j in range(lev + 1):\n\t\t\t\tif name[0] in levels[j]:\n\t\t\t\t\tgov = False\n\t\t\t\t\tbreak\n\t\t\tif gov:\n\t\t\t\tif name[0] not in levels[lev + 1]:\n\t\t\t\t\tlevels[lev + 1][name[0]] = int(name[1])\n\t\t\t\telse:\n\t\t\t\t\tfound = levels[lev + 1][name[0]]\n\t\t\t\t\tlevels[lev + 1][name[0]] = max(int(name[1]), found)\n\tlev += 1\nres = {}\nfor i in range(1, len(levels) - 2):\n\tres.update(levels[i])\nkeys = list(res.keys())\nkeys.sort()\nprint(len(keys))\nfor i in keys:\n\tprint(i + ' ' + str(res[i]))\n", "from collections import defaultdict\nn = int(input())\nd = defaultdict(dict)\nfor i in range(n):\n\tx = input()\n\tx = x.split()\n\tif i == 0:\n\t\tP = x\n\tq = int(input())\n\tCon = []\n\tfor j in range(q):\n\t\tCon.append(input().split())\n\tif i != n - 1:\n\t\tinput()\n\td[x[0]][x[1]] = Con\nver = [P]\nans = {}\nwhile ver:\n\tnext_ans = {}\n\tfor v in ver:\n\t\tC = d[v[0]][v[1]]\n\t\tfor n_v in C:\n\t\t\tif n_v[0] not in ans and n_v[0] != P[0]:\n\t\t\t\tif n_v[0] in next_ans:\n\t\t\t\t\tif int(n_v[1]) > int(next_ans[n_v[0]]):\n\t\t\t\t\t\tnext_ans[n_v[0]] = n_v[1]\n\t\t\t\telse:\n\t\t\t\t\tnext_ans[n_v[0]] = n_v[1]\n\tans.update(next_ans)\n\tver = list(next_ans.items())\nl = list(ans.items())\nprint(len(l))\nl.sort()\nfor (k, v) in l:\n\tprint(k, v)\n", "N = int(input())\nSlide = dict()\nSlideList = [list()] * N\nItogInformation = set()\nGoodNameTags = set()\n(NewName, NewVer) = input().split()\nNewVer = int(NewVer)\nGoodNameTags.add(NewName)\nSlide[0] = NewName + ' ' + str(NewVer)\nSlide[NewName + ' ' + str(NewVer)] = 0\nNewNum = int(input())\nSlideList[0] = [0] * (NewNum + 2)\nSlideList[0][1] = NewNum\nfor i in range(1, NewNum + 1):\n\t(Name, Ver) = input().split()\n\tSlideList[0][i + 1] = Name + ' ' + Ver\nfor j in range(1, N):\n\tinput()\n\t(NewName, NewVer) = input().split()\n\tNewVer = int(NewVer)\n\tSlide[j] = NewName + ' ' + str(NewVer)\n\tSlide[NewName + ' ' + str(NewVer)] = j\n\tNewNum = int(input())\n\tSlideList[j] = [0] * (NewNum + 2)\n\tSlideList[j][1] = NewNum\n\tfor i in range(1, NewNum + 1):\n\t\t(Name, Ver) = input().split()\n\t\tSlideList[j][i + 1] = Name + ' ' + Ver\nListOfNeed = set()\nListOfRead = set()\nListOfRead.add(Slide[0])\nwhile len(ListOfRead) != 0:\n\tListOfNeed = ListOfRead.copy()\n\tListOfRead = set()\n\tfound = dict()\n\tfor i in ListOfNeed:\n\t\tfor j in range(SlideList[Slide[i]][1]):\n\t\t\t(Name, Ver) = SlideList[Slide[i]][j + 2].split()\n\t\t\tVer = int(Ver)\n\t\t\tkey = found.pop(Name, -1)\n\t\t\tif key == -1 or key < Ver:\n\t\t\t\tfound[Name] = Ver\n\t\t\telse:\n\t\t\t\tfound[Name] = key\n\tfor i in list(found.keys()):\n\t\tif not i in GoodNameTags:\n\t\t\tGoodNameTags.add(i)\n\t\t\tListOfRead.add(i + ' ' + str(found[i]))\n\t\t\tItogInformation.add(i + ' ' + str(found[i]))\nOtvet = list(ItogInformation)\nOtvet.sort()\nprint(len(Otvet))\nfor i in range(len(Otvet)):\n\tprint(Otvet[i])\n", "def bfs(polycarp, all_projects, existed_projects):\n\tqueue0 = {polycarp[0]: polycarp[1]}\n\tqueue1 = {}\n\twhile queue0:\n\t\tfor p in list(queue0.items()):\n\t\t\texisted_projects[p[0]] = p[1]\n\t\tfor pp in list(queue0.items()):\n\t\t\tfor p in all_projects[pp]:\n\t\t\t\tif p[0] not in existed_projects:\n\t\t\t\t\tif p[0] not in queue1:\n\t\t\t\t\t\tqueue1[p[0]] = p[1]\n\t\t\t\t\telse:\n\t\t\t\t\t\tqueue1[p[0]] = max(queue1[p[0]], p[1])\n\t\t\t\telse:\n\t\t\t\t\tcontinue\n\t\t(queue0, queue1) = (queue1, {})\n\ndef main():\n\tn = int(input())\n\tall_projects = {}\n\tfor _ in range(n):\n\t\t(name, version) = input().split()\n\t\tversion = int(version)\n\t\tif _ == 0:\n\t\t\tpolycarp = (name, version)\n\t\tnn = int(input())\n\t\tall_projects[name, version] = []\n\t\tfor _2 in range(nn):\n\t\t\t(name2, version2) = input().split()\n\t\t\tversion2 = int(version2)\n\t\t\tall_projects[name, version].append((name2, version2))\n\t\tif _ != n - 1:\n\t\t\tinput()\n\texisted_projects = {}\n\tbfs(polycarp, all_projects, existed_projects)\n\tprint(len(existed_projects) - 1)\n\tfor name in sorted(existed_projects.keys()):\n\t\tif name != polycarp[0]:\n\t\t\tprint(name, existed_projects[name])\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "n = int(input())\nd = {}\nfor x in range(n):\n\t(l, r) = list(map(str, input().split()))\n\tr = int(r)\n\tif x == 0:\n\t\tL = l\n\t\tR = r\n\tif not (l, r) in d:\n\t\td[l, r] = []\n\tm = int(input())\n\tfor y in range(m):\n\t\t(l1, r1) = list(map(str, input().split()))\n\t\td[l, r].append((l1, int(r1)))\n\tif x != n - 1:\n\t\ts = input()\nlst = []\narray = [L]\ntemp1 = [(L, R)]\ntemp2 = []\nk1 = 0\nk2 = 1\nwhile k1 < len(temp1) or k2 < len(temp2):\n\tif k2 > len(temp2):\n\t\twhile k1 < len(temp1):\n\t\t\tfor (a, b) in d[temp1[k1]]:\n\t\t\t\ttemp2.append((a, -b))\n\t\t\tk1 += 1\n\t\ttemp2.sort()\n\t\ttemp = []\n\t\tfor (a, b) in temp2:\n\t\t\tif not a in array:\n\t\t\t\tarray.append(a)\n\t\t\t\tlst.append((a, -b))\n\t\t\t\ttemp.append((a, -b))\n\t\ttemp2 = temp[:]\n\t\ttemp1 = []\n\t\tk1 = 1\n\t\tk2 = 0\n\telif k1 > len(temp1):\n\t\twhile k2 < len(temp2):\n\t\t\tfor (a, b) in d[temp2[k2]]:\n\t\t\t\ttemp1.append((a, -b))\n\t\t\tk2 += 1\n\t\ttemp1.sort()\n\t\ttemp = []\n\t\tfor (a, b) in temp1:\n\t\t\tif not a in array:\n\t\t\t\tarray.append(a)\n\t\t\t\tlst.append((a, -b))\n\t\t\t\ttemp.append((a, -b))\n\t\ttemp1 = temp[:]\n\t\ttemp2 = []\n\t\tk2 = 1\n\t\tk1 = 0\nlst.sort()\nprint(len(lst))\nfor (a, b) in lst:\n\tprint(a, b)\n", "def readline():\n\treturn input()\n\ndef read_project():\n\tproject = readline().split(' ')\n\tproject[1] = int(project[1])\n\tdep_num = int(readline())\n\tdeps = {}\n\tfor _ in range(0, dep_num):\n\t\t(proj, version) = readline().split(' ')\n\t\tversion = int(version)\n\t\tif proj in deps:\n\t\t\tdeps[proj] = max(deps[proj], version)\n\t\telse:\n\t\t\tdeps[proj] = version\n\treturn (tuple(project), deps)\n\ndef make_like_buck():\n\tprojects_num = int(readline())\n\tprojects = {}\n\tpolikarp_proj = None\n\tfor ind in range(0, projects_num):\n\t\t(proj, deps) = read_project()\n\t\tif ind == 0:\n\t\t\tpolikarp_proj = proj\n\t\tprojects[proj] = deps\n\t\tif ind != projects_num - 1:\n\t\t\treadline()\n\tRESULT_DEPS = {polikarp_proj[0]: polikarp_proj[1]}\n\tcurr_proj = [polikarp_proj]\n\twhile len(curr_proj) > 0:\n\t\tcurr_deps = {}\n\t\tfor proj in curr_proj:\n\t\t\tnew_deps = projects[proj]\n\t\t\tfor proj in new_deps:\n\t\t\t\tif proj in RESULT_DEPS:\n\t\t\t\t\tcontinue\n\t\t\t\tif proj in curr_deps:\n\t\t\t\t\tcurr_deps[proj] = max(curr_deps[proj], new_deps[proj])\n\t\t\t\telse:\n\t\t\t\t\tcurr_deps[proj] = new_deps[proj]\n\t\tRESULT_DEPS = {**RESULT_DEPS, **curr_deps}\n\t\tcurr_proj = list(curr_deps.items())\n\tRESULT_DEPS.pop(polikarp_proj[0])\n\tprint(len(RESULT_DEPS))\n\titems = ['%s %s' % x for x in sorted(list(RESULT_DEPS.items()))]\n\tprint('\\n'.join(items))\nmake_like_buck()\n", "def read_project_name():\n\t(name, version) = input().split()\n\treturn (name, int(version))\n\ndef read_project():\n\tproject = read_project_name()\n\tdeps = list()\n\tdependencies = int(input())\n\twhile dependencies:\n\t\tdependencies -= 1\n\t\tdeps.append(read_project_name())\n\treturn (project, tuple(deps))\n\ndef main():\n\tdependencies = dict()\n\tn = int(input()) - 1\n\t(main_project, deps) = read_project()\n\tdependencies[main_project] = deps\n\tqueue = (main_project,)\n\twhile n:\n\t\tn -= 1\n\t\tinput()\n\t\t(project, deps) = read_project()\n\t\tdependencies[project] = deps\n\tselected = dict()\n\twhile queue:\n\t\tnew_selected = dict()\n\t\tfor (name, version) in queue:\n\t\t\tif name not in selected:\n\t\t\t\told = new_selected.get(name, -1)\n\t\t\t\tnew_selected[name] = max(old, version)\n\t\tqueue = list()\n\t\tfor project in new_selected.items():\n\t\t\tqueue.extend(dependencies[project])\n\t\tselected.update(new_selected)\n\tdel selected[main_project[0]]\n\tprint(len(selected))\n\tfor (project, ver) in sorted(selected.items()):\n\t\tprint(project, ver)\nmain()\n", "n = int(input())\nprojects = {}\nroot = None\nfor i in range(n):\n\t(name, v) = input().split()\n\tv = int(v)\n\tprojects[name, v] = []\n\tm = int(input())\n\tfor j in range(m):\n\t\t(nn, vv) = input().split()\n\t\tvv = int(vv)\n\t\tprojects[name, v].append((nn, vv))\n\tif i < n - 1:\n\t\tinput()\n\tif not i:\n\t\troot = (name, v)\nq = set([root])\nans = {}\nwhile q:\n\ttemp = {}\n\tfor u in q:\n\t\tfor v in projects[u]:\n\t\t\tif v[0] not in ans and v[0] != root[0]:\n\t\t\t\tif v[0] not in temp:\n\t\t\t\t\ttemp[v[0]] = v[1]\n\t\t\t\telse:\n\t\t\t\t\ttemp[v[0]] = max(temp[v[0]], v[1])\n\tans.update(temp.items())\n\tq = set(temp.items())\nprint(len(ans))\nprint('\\n'.join(list(map(lambda x: ' '.join((str(c) for c in x)), sorted(list(ans.items()), key=lambda item: item[0])))))\n", "def read_pack():\n\t(name, ver) = input().strip().split()\n\treturn (name, int(ver))\nn = int(input())\ndeps = dict()\nfor i in range(n):\n\tpack = read_pack()\n\tif not i:\n\t\troot = pack\n\tdep_n = int(input())\n\tdeps[pack] = [read_pack() for _ in range(dep_n)]\n\tif i != n - 1:\n\t\tinput()\nqueue = [(root, 0)]\ntaken = {root[0]: (root[1], 0)}\nfor (pack, level) in queue:\n\tif pack[0] in taken and pack[1] != taken[pack[0]][0]:\n\t\tcontinue\n\tfor dep in deps[pack]:\n\t\tif dep[0] not in taken or (taken[dep[0]][1] == level + 1 and taken[dep[0]][0] < dep[1]):\n\t\t\ttaken[dep[0]] = (dep[1], level + 1)\n\t\t\tqueue.append((dep, level + 1))\ndel taken[root[0]]\nprint(len(taken))\nfor d in sorted(taken):\n\tprint(d, taken[d][0])\n", "from queue import Queue\n\ndef main():\n\tn = int(input())\n\td = {}\n\tres = {}\n\tstart = None\n\tfor i in range(n):\n\t\t(project, version) = input().split()\n\t\tversion = int(version)\n\t\tif i == 0:\n\t\t\tstart = (project, version)\n\t\tk = int(input())\n\t\tif project not in d:\n\t\t\td[project] = {}\n\t\tif version not in d[project]:\n\t\t\td[project][version] = []\n\t\tfor j in range(k):\n\t\t\t(p, v) = input().split()\n\t\t\tv = int(v)\n\t\t\td[project][version].append((p, v))\n\t\tif i != n - 1:\n\t\t\tinput()\n\tq = Queue()\n\tq.put(start)\n\tk = 1\n\twhile not q.empty():\n\t\tappend = {}\n\t\tfor i in range(k):\n\t\t\t(s_p, s_v) = q.get()\n\t\t\tfor (p, v) in d[s_p][s_v]:\n\t\t\t\tif p == start[0]:\n\t\t\t\t\tcontinue\n\t\t\t\tif p in res:\n\t\t\t\t\tcontinue\n\t\t\t\tif p not in append or append[p] < v:\n\t\t\t\t\tappend[p] = v\n\t\tk = len(append)\n\t\tfor p in append:\n\t\t\tres[p] = append[p]\n\t\t\tq.put((p, append[p]))\n\tans = []\n\tfor p in res:\n\t\tv = res[p]\n\t\tans.append((p, v))\n\tans = sorted(ans, key=lambda z: z[0])\n\tprint(len(ans))\n\tfor (p, v) in ans:\n\t\tprint(p, v)\nmain()\n", "from queue import Queue\n\ndef BFS(v):\n\tnonlocal ans\n\tstack = Queue()\n\tstack.put(v)\n\tused = {p[0]: False for p in list(graph.keys())}\n\tused[v[0]] = True\n\twhile True:\n\t\tset_ = dict()\n\t\tst = Queue()\n\t\twhile not stack.empty():\n\t\t\tv = stack.get()\n\t\t\tfor u in graph[v]:\n\t\t\t\tn_ = u[0]\n\t\t\t\tif not used[n_]:\n\t\t\t\t\ttry:\n\t\t\t\t\t\tset_[n_] = max(set_[n_], u[1])\n\t\t\t\t\texcept KeyError:\n\t\t\t\t\t\tset_[n_] = u[1]\n\t\tfor el in list(set_.items()):\n\t\t\tans.append(el)\n\t\t\tst.put(el)\n\t\t\tused[el[0]] = True\n\t\tif st.empty():\n\t\t\tbreak\n\t\twhile not st.empty():\n\t\t\tstack.put(st.get())\nn = int(input())\ngraph = dict()\nfor i in range(n):\n\t(name, ver) = input().split()\n\tk = int(input())\n\ttemp = set()\n\tfor j in range(k):\n\t\t(name_, ver_) = input().split()\n\t\ttemp.add((name_, int(ver_)))\n\ttup = (name, int(ver))\n\tgraph[tup] = temp\n\tif i == 0:\n\t\tPP = tup\n\tif i + 1 != n:\n\t\tinput()\nans = list()\nBFS(PP)\nprint(len(ans))\nprint('\\n'.join([' '.join(map(str, el)) for el in sorted(ans, key=lambda x: x[0])]))\n", "from sys import stdin, stdout\n\ndef read_pack():\n\t(name, ver) = stdin.readline().split()\n\treturn (name, int(ver))\nn = int(input())\ndeps = dict()\nfor i in range(n):\n\tpack = read_pack()\n\tif not i:\n\t\troot = pack\n\tdep_n = int(input())\n\tdeps[pack] = [read_pack() for _ in range(dep_n)]\n\tif i != n - 1:\n\t\tinput()\nqueue = [(root, 0)]\ntaken = {root[0]: (root[1], 0)}\nfor (pack, level) in queue:\n\tfor dep in deps[pack]:\n\t\tif dep[0] not in taken:\n\t\t\ttaken[dep[0]] = (dep[1], level + 1)\n\t\t\tqueue.append((dep, level + 1))\n\t\telif taken[dep[0]][1] == level + 1 and taken[dep[0]][0] < dep[1]:\n\t\t\tindex = queue.index(((dep[0], taken[dep[0]][0]), level + 1))\n\t\t\ttaken[dep[0]] = (dep[1], level + 1)\n\t\t\tqueue[index] = (dep, level + 1)\ndel taken[root[0]]\nprint(len(taken))\nfor d in sorted(taken):\n\tprint(d, taken[d][0])\n"]

difficulty: MEDIUM

source: codeforces

sample_tests: {"inputs": ["4\na 3\n2\nb 1\nc 1\n\u00a0\nb 2\n0\n\u00a0\nb 1\n1\nb 2\n\u00a0\nc 1\n1\nb 2", "9\ncodehorses 5\n3\nwebfrmk 6\nmashadb 1\nmashadb 2\n\u00a0\ncommons 2\n0\n\u00a0\nmashadb 3\n0\n\u00a0\nwebfrmk 6\n2\nmashadb 3\ncommons 2\n\u00a0\nextra 4\n1\nextra 3\n\u00a0\nextra 3\n0\n\u00a0\nextra 1\n0\n\u00a0\nmashadb 1\n1\nextra 3\n\u00a0\nmashadb 2\n1\nextra 1", "3\nabc 1\n2\nabc 3\ncba 2\nabc 3\n0\ncba 2\n0"], "outputs": ["2\nb 1\nc 1", "4\ncommons 2\nextra 1\nmashadb 2\nwebfrmk 6", "1\ncba 2"]}

raw_problem:
C. Dependency management

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Polycarp is currently developing a project in Vaja language and using a popular dependency management system called Vamen. From Vamen's point of view both Vaja project and libraries are treated projects for simplicity.

A project in Vaja has its own uniqie non-empty name consisting of lowercase latin letters with length not exceeding 10 and version — positive integer from 1 to 106. Each project (keep in mind that it is determined by both its name and version) might depend on other projects. For sure, there are no cyclic dependencies.

You're given a list of project descriptions. The first of the given projects is the one being developed by Polycarp at this moment. Help Polycarp determine all projects that his project depends on (directly or via a certain chain).

It's possible that Polycarp's project depends on two different versions of some project. In this case collision resolving is applied, i.e. for each such project the system chooses the version that minimizes the distance from it to Polycarp's project. If there are several options, the newer (with the maximum version) is preferred. This version is considered actual; other versions and their dependencies are ignored.

More formal, choose such a set of projects of minimum possible size that the following conditions hold:

 Polycarp's project is chosen;

 Polycarp's project depends (directly or indirectly) on all other projects in the set;

 no two projects share the name;

 for each project x that some other project in the set depends on we have either x or some y with other version and shorter chain to Polycarp's project chosen. In case of ties the newer one is chosen.

Output all Polycarp's project's dependencies (Polycarp's project itself should't be printed) in lexicographical order.

Input

The first line contains an only integer n (1 ≤ n ≤ 1 000) — the number of projects in Vaja.

The following lines contain the project descriptions. Each project is described by a line consisting of its name and version separated by space. The next line gives the number of direct dependencies (from 0 to n - 1) and the dependencies themselves (one in a line) in arbitrary order. Each dependency is specified by its name and version. The projects are also given in arbitrary order, but the first of them is always Polycarp's. Project descriptions are separated by one empty line. Refer to samples for better understanding.

It's guaranteed that there are no cyclic dependencies.

Output

Output all Polycarp's project's dependencies in lexicographical order.

Examples

Input

4
a 3
2
b 1
c 1

b 2
0

b 1
1
b 2

c 1
1
b 2

Output

2
b 1
c 1

Input

9
codehorses 5
3
webfrmk 6
mashadb 1
mashadb 2

commons 2
0

mashadb 3
0

webfrmk 6
2
mashadb 3
commons 2

extra 4
1
extra 3

extra 3
0

extra 1
0

mashadb 1
1
extra 3

mashadb 2
1
extra 1

Output

4
commons 2
extra 1
mashadb 2
webfrmk 6

Input

3
abc 1
2
abc 3
cba 2

abc 3
0

cba 2
0

Output

1
cba 2

Note

The first sample is given in the pic below. Arrow from A to B means that B directly depends on A. Projects that Polycarp's project «a» (version 3) depends on are painted black.

The second sample is again given in the pic below. Arrow from A to B means that B directly depends on A. Projects that Polycarp's project «codehorses» (version 5) depends on are paint it black. Note that «extra 1» is chosen instead of «extra 3» since «mashadb 1» and all of its dependencies are ignored due to «mashadb 2».

question:
Polycarp is currently developing a project in Vaja language and using a popular dependency management system called Vamen. From Vamen's point of view both Vaja project and libraries are treated projects for simplicity.
A project in Vaja has its own uniqie non-empty name consisting of lowercase latin letters with length not exceeding 10 and version — positive integer from 1 to 10^{6}. Each project (keep in mind that it is determined by both its name and version) might depend on other projects. For sure, there are no cyclic dependencies.
You're given a list of project descriptions. The first of the given projects is the one being developed by Polycarp at this moment. Help Polycarp determine all projects that his project depends on (directly or via a certain chain).
It's possible that Polycarp's project depends on two different versions of some project. In this case collision resolving is applied, i.e. for each such project the system chooses the version that minimizes the distance from it to Polycarp's project. If there are several options, the newer (with the maximum version) is preferred. This version is considered actual; other versions and their dependencies are ignored.
More formal, choose such a set of projects of minimum possible size that the following conditions hold:
 -  Polycarp's project is chosen; -  Polycarp's project depends (directly or indirectly) on all other projects in the set; -  no two projects share the name; -  for each project x that some other project in the set depends on we have either x or some y with other version and shorter chain to Polycarp's project chosen. In case of ties the newer one is chosen. Output all Polycarp's project's dependencies (Polycarp's project itself should't be printed) in lexicographical order.

Input
The first line contains an only integer n (1 ≤ n ≤ 1 000) — the number of projects in Vaja.
The following lines contain the project descriptions. Each project is described by a line consisting of its name and version separated by space. The next line gives the number of direct dependencies (from 0 to n - 1) and the dependencies themselves (one in a line) in arbitrary order. Each dependency is specified by its name and version. The projects are also given in arbitrary order, but the first of them is always Polycarp's. Project descriptions are separated by one empty line. Refer to samples for better understanding.
It's guaranteed that there are no cyclic dependencies.

Output
Output all Polycarp's project's dependencies in lexicographical order.

Examples
Input
4
a 3
2
b 1
c 1

b 2
0

b 1
1
b 2

c 1
1
b 2

Output
2
b 1
c 1

Input
9
codehorses 5
3
webfrmk 6
mashadb 1
mashadb 2

commons 2
0

mashadb 3
0

webfrmk 6
2
mashadb 3
commons 2

extra 4
1
extra 3

extra 3
0

extra 1
0

mashadb 1
1
extra 3

mashadb 2
1
extra 1

Output
4
commons 2
extra 1
mashadb 2
webfrmk 6

Input
3
abc 1
2
abc 3
cba 2

abc 3
0

cba 2
0

Output
1
cba 2

Note
The first sample is given in the pic below. Arrow from A to B means that B directly depends on A. Projects that Polycarp's project «a» (version 3) depends on are painted black.
 ![image](1.png) The second sample is again given in the pic below. Arrow from A to B means that B directly depends on A. Projects that Polycarp's project «codehorses» (version 5) depends on are paint it black. Note that «extra 1» is chosen instead of «extra 3» since «mashadb 1» and all of its dependencies are ignored due to «mashadb 2».
 ![image](2.png)

image_tags: Graph Graph

data_split: test


D. Recovering BST

problem_index: D

time_limit: 1 second

memory_limit: 256 megabytes

note:
The picture below illustrates one of the possible trees for the first example.
![image](images/cf_1025_D/1.png)
The picture below illustrates one of the possible trees for the third example.
![image](images/cf_1025_D/2.png)

solutions: ["from math import gcd\nimport random, time, sys\ninput = sys.stdin.buffer.readline\n\ndef main():\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tstart = time.time()\n\tGCD = [1 << i for i in range(n + 1)]\n\tfor i in range(n):\n\t\tfor j in range(i):\n\t\t\tif gcd(a[i], a[j]) > 1:\n\t\t\t\tGCD[i] += 1 << j\n\t\t\t\tGCD[j] += 1 << i\n\tcheck1 = [1 << j for j in range(n + 1)]\n\tcheck2 = [1 << j for j in range(n + 1)]\n\tfor i in range(n):\n\t\tcheck1[0] |= int(bool(check1[0] & check2[i] & GCD[i + 1])) * (1 << i + 1)\n\t\tfor j in range(1, n - i):\n\t\t\tcheck1[j] |= int(bool(check1[j] & check2[i + j] & GCD[j + i + 1])) * (1 << i + j + 1)\n\t\t\tcheck2[j + i] |= int(bool(check1[j] & check2[i + j] & GCD[j - 1])) * (1 << j - 1)\n\tans = bool(check1[0] & check2[n - 1])\n\tprint('Yes' if ans else 'No')\nmain()\n", "from sys import stdin\nfrom math import gcd\nn = int(stdin.readline())\na = [int(x) for x in stdin.readline().split()]\nc = []\nld = []\nrd = []\n\ndef check(l, r, e):\n\tif r == l:\n\t\treturn c[l][e] > 0\n\tif e < l and ld[l][r - l] != 0:\n\t\treturn ld[l][r - l] == 1\n\telif e > r and rd[l][r - l] != 0:\n\t\treturn rd[l][r - l] == 1\n\tfor i in range(l, r + 1):\n\t\tif c[i][e] > 0:\n\t\t\tif i == l or check(l, i - 1, i):\n\t\t\t\tif i == r or check(i + 1, r, i):\n\t\t\t\t\tif e < l:\n\t\t\t\t\t\tld[l][r - l] = 1\n\t\t\t\t\telse:\n\t\t\t\t\t\trd[l][r - l] = 1\n\t\t\t\t\treturn True\n\tif e < l:\n\t\tld[l][r - l] = -1\n\telse:\n\t\trd[l][r - l] = -1\n\treturn False\nfor i in range(n):\n\tc.append([0] * n)\n\tld.append([0] * n)\n\trd.append([0] * n)\nfor i in range(n):\n\tfor j in range(i + 1, n):\n\t\tif gcd(a[i], a[j]) > 1:\n\t\t\tc[i][j] = c[j][i] = 1\nans = False\nfor i in range(n):\n\tif i == 0 or check(0, i - 1, i):\n\t\tif i == n - 1 or check(i + 1, n - 1, i):\n\t\t\tans = True\n\t\t\tbreak\nif ans:\n\tprint('Yes')\nelse:\n\tprint('No')\n"]

difficulty: HARD

source: codeforces

raw_problem:
D. Recovering BST

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!

Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset.

To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed $$$1$$$.

Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found here.

Input

The first line contains the number of vertices $$$n$$$ ($$$2 \le n \le 700$$$).

The second line features $$$n$$$ distinct integers $$$a_i$$$ ($$$2 \le a_i \le 10^9$$$) — the values of vertices in ascending order.

Output

If it is possible to reassemble the binary search tree, such that the greatest common divisor of any two vertices connected by the edge is greater than $$$1$$$, print "Yes" (quotes for clarity).

Otherwise, print "No" (quotes for clarity).

Examples

Input

6
3 6 9 18 36 108

Output

Yes

Input

2
7 17

Output

No

Input

9
4 8 10 12 15 18 33 44 81

Output

Yes

Note

The picture below illustrates one of the possible trees for the first example.

The picture below illustrates one of the possible trees for the third example.

question:
Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!
Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset.
To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed $$$1$$$.
Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found here.

Input
The first line contains the number of vertices $$$n$$$ ($$$2 \le n \le 700$$$).
The second line features $$$n$$$ distinct integers $$$a_i$$$ ($$$2 \le a_i \le 10^9$$$) — the values of vertices in ascending order.

Output
If it is possible to reassemble the binary search tree, such that the greatest common divisor of any two vertices connected by the edge is greater than $$$1$$$, print "Yes" (quotes for clarity).
Otherwise, print "No" (quotes for clarity).

Examples
Input
6
3 6 9 18 36 108

Output
Yes

Input
2
7 17

Output
No

Input
9
4 8 10 12 15 18 33 44 81

Output
Yes

Note
The picture below illustrates one of the possible trees for the first example.
 ![image](1.png) The picture below illustrates one of the possible trees for the third example.
 ![image](2.png)

tags: ['Complete search', 'Number theory', 'Tree algorithms', 'Dynamic programming', 'Mathematics']

skill_types: ['Dynamic programming', 'Complete search']

raw_tags: ['math', 'dp', 'trees', 'brute force', 'number theory']

image_tags: Tree Tree

data_split: test


Tunnel

source: University of Aizu Programming Contest 2019, Ritsumeikan University Competitive Programming Camp 2019

raw_problem:
Problem D: Tunnel

Problem

  横軸$x$、縦軸$y$の$xy$平面上に$n$個の長方形がある。$i$番目の長方形は、高さ$h_i$、幅$1$であり、頂点は点$(i-1, 0)$、点$(i-1, h_i)$、点$(i, h_i)$、点$(i, 0)$である。

  あなたは$n$個の正の整数$y_1, y_2, ... y_n$を選び、以下の$n$回の操作を行う。

  (1) 1回目の操作では、点$(0, 1)$と点$(1, y_1)$を結ぶ線分を引く。

  (2) $i$回目$(2 \le i \le n)$の操作では、点$(i-1, y_{i-1})$と点$(i, y_i)$を結ぶ線分を引く。

  $i$回目の操作に対し、$S_i$を以下のように定める。

  $i$回目の操作で引いた線分の$x$座標が小さい方の端点をA、$x$座標が大きい方の端点をBとする。

  また、点$(i-1, 0)$をC、点$(i-1, h_i)$をD、点$(i, h_i)$をE 、点$(i, 0)$をFとする。

  台形ABFCと長方形DEFCの非共通部分の面積を$S_i$とする。

  以下に５つの例を示す。

  それぞれの例における$S_i$は星マークを含む領域の面積の合計である。

  $S = S_1 + S_2 + … + S_n$を最小化するような$y_1, y_2, ... y_n$を求め、$S$の最小値を出力せよ。

Input

入力は以下の形式で与えられる。

$n$
$h_1$ $h_2$ $...$ $h_n$

  入力はすべて整数で与えられる。

Constraints

入力は以下の条件を満たす。

$2 \leq n \leq 150 $

$1 \leq h_i \leq 150 $

Output

  $S$の最小値を1行に出力せよ。

  ただし、$10^{−5}$ までの絶対誤差または相対誤差は許容される。

Sample Input 1

2
5 3

Sample Output 1

2.83333333

Sample Input 2

3
6 1 4

Sample Output 2

6.25000000

Sample Input 3

7
3 1 9 2 2 5 1

Sample Output 3

12.37500000

source: aizu

question:
Problem D: Tunnel
Problem

  On the $xy$-plane with the horizontal axis $x$ and vertical axis $y$, there are $n$ rectangles. The $i$th rectangle has a height of $h_i$ and a width of $1$, with vertices at the points $(i-1, 0)$, $(i-1, h_i)$, $(i, h_i)$, and $(i, 0)$.

  You will choose $n$ positive integers $y_1, y_2, ... y_n$ and perform the following $n$ operations.

  (1) In the first operation, draw a line segment connecting point $(0, 1)$ and point $(1, y_1)$.
  (2) In the $i$th operation $(2 \le i \le n)$, draw a line segment connecting point $(i-1, y_{i-1})$ and point $(i, y_i)$.

  For the $i$th operation, $S_i$ is defined as follows.

  Let A be the endpoint with the smaller $x$ coordinate and B the endpoint with the larger $x$ coordinate of the line segment drawn in the $i$th operation.
  Also, let point $(i-1, 0)$ be C, point $(i-1, h_i)$ be D, point $(i, h_i)$ be E, and point $(i, 0)$ be F.
  Define $S_i$ as the area of the non-common parts of trapezoid ABFC and rectangle DEFC.

  Below are five examples.
![image](1.png)
  In each example, $S_i$ is the total area of the regions marked with a star.

  Find $y_1, y_2, ... y_n$ that minimizes $S = S_1 + S_2 + … + S_n$, and output the minimum value of $S$.

Input
The input is given in the following format:

$n$
$h_1$ $h_2$ $...$ $h_n$

  All inputs are given as integers.

Constraints
The input satisfies the following conditions.

- $2 \leq n \leq 150 $
- $1 \leq h_i \leq 150 $

Output

  Output the minimum value of $S$ in one line.
  However, an absolute or relative error up to $10^{−5}$ is acceptable.

Sample Input 1

2
5 3

Sample Output 1

2.83333333

Sample Input 2

3
6 1 4

Sample Output 2

6.25000000

Sample Input 3

7
3 1 9 2 2 5 1

Sample Output 3

12.37500000

data_split: test


Dragon's Cruller

source: ACM International Collegiate Programming Contest, Asia Regional 2013, Japan

raw_problem:
Problem E: Dragon's Cruller

Dragon's Cruller is a sliding puzzle on a torus. The torus surface is partitioned into nine squares as shown in its development in Figure E.1. Here, two squares with one of the sides on the development labeled with the same letter are adjacent to each other, actually sharing the side. Figure E.2 shows which squares are adjacent to which and in which way. Pieces numbered from 1 through 8 are placed on eight out of the nine squares, leaving the remaining one empty.

Figure E.1. A 3 × 3 Dragon’s Cruller torus

A piece can be slid to an empty square from one of its adjacent squares. The goal of the puzzle is, by sliding pieces a number of times, to reposition the pieces from the given starting arrangement into the given goal arrangement. Figure E.3 illustrates arrangements directly reached from the arrangement shown in the center after four possible slides. The cost to slide a piece depends on the direction but is independent of the position nor the piece.

Your mission is to find the minimum cost required to reposition the pieces from the given starting
arrangement into the given goal arrangement.

Figure E.2. Adjacency

Figure E.3. Examples of sliding steps

Unlike some sliding puzzles on a flat square, it is known that any goal arrangement can be reached from any starting arrangements on this torus.

Input

The input is a sequence of at most 30 datasets.

A dataset consists of seven lines. The first line contains two positive integers <var>ch</var> and <var>cv</var>, which represent the respective costs to move a piece horizontally and vertically. You can assume that
both <var>ch</var> and <var>cv</var> are less than 100. The next three lines specify the starting arrangement and the last three the goal arrangement, each in the following format.

<var>dA</var> <var>dB</var> <var>dC</var>
<var>dD</var> <var>dE</var> <var>dF</var>
<var>dG</var> <var>dH</var> <var>dI</var>

Each line consists of three digits separated by a space. The digit <var>dX</var> (<var>X</var> is one of <var>A</var> through <var>I</var>) indicates the state of the square <var>X</var> as shown in Figure E.2. Digits 1, . . . , 8 indicate that the piece of that number is on the square. The digit 0 indicates that the square is empty.

The end of the input is indicated by two zeros separated by a space.

Output

For each dataset, output the minimum total cost to achieve the goal, in a line. The total cost is the sum of the costs of moves from the starting arrangement to the goal arrangement. No other characters should appear in the output.

Sample Input

4 9
6 3 0
8 1 2
4 5 7
6 3 0
8 1 2
4 5 7
31 31
4 3 6
0 1 5
8 2 7
0 3 6
4 1 5
8 2 7
92 4
1 5 3
4 0 7
8 2 6
1 5 0
4 7 3
8 2 6
12 28
3 4 5
0 2 6
7 1 8
5 7 1
8 6 2
0 3 4
0 0

Output for the Sample Input

0
31
96
312

source: aizu

question:
Problem E: Dragon's Cruller

Dragon's Cruller is a sliding puzzle on a torus. The torus surface is partitioned into nine squares as shown in its development in Figure E.1. Here, two squares with one of the sides on the development labeled with the same letter are adjacent to each other, actually sharing the side. Figure E.2 shows which squares are adjacent to which and in which way. Pieces numbered from 1 through 8 are placed on eight out of the nine squares, leaving the remaining one empty.

![image](1.png)

Figure E.1. A 3 × 3 Dragon’s Cruller torus

A piece can be slid to an empty square from one of its adjacent squares. The goal of the puzzle is, by sliding pieces a number of times, to reposition the pieces from the given starting arrangement into the given goal arrangement. Figure E.3 illustrates arrangements directly reached from the arrangement shown in the center after four possible slides. The cost to slide a piece depends on the direction but is independent of the position nor the piece.

Your mission is to find the minimum cost required to reposition the pieces from the given starting
arrangement into the given goal arrangement.

![image](2.png)

Figure E.2. Adjacency

![image](3.png)

Figure E.3. Examples of sliding steps

Unlike some sliding puzzles on a flat square, it is known that any goal arrangement can be reached from any starting arrangements on this torus.

Input

The input is a sequence of at most 30 datasets.

A dataset consists of seven lines. The first line contains two positive integers $c_{h}$ and $c_{v}$, which represent the respective costs to move a piece horizontally and vertically. You can assume that
both $c_{h}$ and $c_{v}$ are less than 100. The next three lines specify the starting arrangement and the last three the goal arrangement, each in the following format.

$dA$ $dB$ $dC$

$dD$ $dE$ $dF$

$dG$ $dH$ $dI$

Each line consists of three digits separated by a space. The digit $d_{X}$ ($X$ is one of $A$ through $I$) indicates the state of the square $X$ as shown in Figure E.2. Digits 1, . . . , 8 indicate that the piece of that number is on the square. The digit 0 indicates that the square is empty.

The end of the input is indicated by two zeros separated by a space.

Output

For each dataset, output the minimum total cost to achieve the goal, in a line. The total cost is the sum of the costs of moves from the starting arrangement to the goal arrangement. No other characters should appear in the output.

Sample Input

4 9
6 3 0
8 1 2
4 5 7
6 3 0
8 1 2
4 5 7
31 31
4 3 6
0 1 5
8 2 7
0 3 6
4 1 5
8 2 7
92 4
1 5 3
4 0 7
8 2 6
1 5 0
4 7 3
8 2 6
12 28
3 4 5
0 2 6
7 1 8
5 7 1
8 6 2
0 3 4
0 0

Output for the Sample Input

0
31
96
312

image_tags: Chessboard Table Chessboard

data_split: test