![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAIAAAACACAYAAADDPmHLAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAADdgAAA3YBfdWCzAAAABl0RVh0U29mdHdhcmUAd3d3Lmlua3NjYXBlLm9yZ5vuPBoAAA6bSURBVHic7Z17cFTVAYd/5+zdzTsQgQYUkEBMsjoEg49SZjodShAftVPBVlvbqcqr2mmto21p/YOhU+zSdlqmnU4DOj5rbcei8qqtgsGZTrUqrElMAms0UkIQAgGqkN37OKd/hIu7m33cu3vuZnfv+WYyk72Pc3f3991zzzn37r2Ecw5JfnPd5ncuMzh9hCn4ZvvK5gGRZVORhUnE0/pIRwMjdC8h+ILCePuiRzuniyxfCpDHLN3S1QRG94LjYgDgnNSLlkAKkMcwxsoIeGn0NNESENkGyG8Wb+mcTzl2c6AmejohvE+nZFG2bQJZA+Q5e1Y372cErQQ4FT1dVE0gBSgAnJRAClAgOCWBFKCA2LO6eT/neDp+ejYSSAEKiNYtHQ+A4PuJ5mUqgRSgQFjS1nU/OPl1qmUykUB2AwuA1s2d9wHYZHV5O11EWQPkOUs2d3wPNsIH7NUEUoA8pnVL13c5yO8yWdeqBFKAPGXJls57wPnvsynDigRSgDykta1jDef4AwCSbVnpJJAC5BlL2rpWgZA/QkD4JqkkkALYIBAMXRoIhh5yqvzWzZ0rOOGbITB8k2QSSAEsEgiGZgJoB/DzQDD0W9HlL97cdReAR+BA+CaJJJACWCAQDE3HaPh15yf9QKQErVs6v03AH4XY8CMguA/AmeiJ8RJIAaxxO4DZcdOESLC4reNb4HgMYrOIAPjK7tXNv+OcX4cUEsiRQIsEgqGNAH6UYNamtS0N92dSZmtb1x0g/Ck4Ef6a5n+YExa3dVxLCHkZwITYRcleKYANAsHQLwH8MMEs2xIs2dL1Dc75UwA8Qt7cKBFOyS17Vs19KX5GAgkGDENZJAWwSSAY+hWABxPMsixBa1vn7SD4E3IUvkmUBB8bhrKo/d7L+6QAGRAIhn4N4IEEs9JKsKSt42uckD8jx+GbLG7ruJYx73D7vZf3AfJsYMYEgqHfAEgUdlIJWjd33grgWQCKwLdiOfxESAGyIBAMPQ7gzgSzxkiwpK1zOSf4CwSHz0CWvbpm7t8zLUB2AzMkEAw1Abg+yeyYLuLito5bOBG/52cbPiBrgIw4H347gKlpFt20583IXg7+HACvwLcgJHxACmAbG+EDAA4fM/SDhzSRe75KCFv2yuord4koTB4CbGA3fACYUetRGmZ6Re1lQsMHpACWySR8k5lTPUSABMLDB6QAlli1vefGY8PsdWQQvkmWEjgSPiC2VVqUrNrec+ORE/oO7SNQAh8+c1Hm+8zMqR4CgIf+q9k566eC8+WvrBEfPiBrgJSY4asaKOdA1/sqjg+zrMq0WROo4Hz57u/M25nVRlMgBUhCIBhq+jjMtqrap9+RSAmaZivpJHA8fEAKkBCzwTd3tq90YmXsVyRCgjNhA54STvz1SY/AKgdudTp8QAowhujWvscDtDT6IFKCM2ED57TR9aiXI4EEKgdu3bOmeUdGH8AmUoAoEnX10klw8ox1CaLDN4mTIKfhA1KAC6Tq5yeToLKcorrC2leYKHwT6uXwX6awXIcPSAEAABveec+PNIM88RJUVVDMb/TBa6EjnSp8E6pwevVc73o771sErj8XsHpH99Jjp/iOufVeb2VZ+u65YQDvHdYxZ7oiLPxoShUa3LjQP9/yClniagFW7uy+fnCI7VJVTr0KwVV+H6xIYBW74ZvkUgLXCrBiW88NR08aO1WNXzgMipQg0/BNciWBK9sAgWCo6ZJaz5OUxn5+TefY16vik5HsdopswweAsM5afvzv3v1ZFWIB1wlgtvbLS8iUq5p8KC2J3duzlUBE+Ca5kMBVAsR39cpKCERKIDJ8E6clcI0Ayfr5oiRwInwTJyVwhQDpLubIVgKR4VMCo0QhPfHTnZKg6AVYtb3nRt3ge5HmYo5UErwTUpGssyQ6/HIvXfrLhZdfUarQ/8TPd0KCohbgru3dXxoYMnYED2i1upG+Kk8kgYcCV9R5QRL0DJ0If8MC/x4A2LjQv6BUoW/GLydagqIVYMWLvTd9NMS2aTqnZ84yBA9osCuBhwJXNvpQUz32a3IyfJONC/2fLVXoW/HLh3XWsvb13qwvCQeKVID1bx6ce+yUvk3TPx3kyUSClqYS1FSNT/gmGxf6ry1V6NvR0zyUqB6CtUK2L6KQfCIQDDWVeMnL/jqvh8ZV23YlmFg5tt7PZfgmGxf6rylV6H5gNPwyhVyzYYG/U8R7KKqh4PjW/skzBjpCGljcR5xQQdHS5IXisTfkOx7hR7P29d5dHoKfiAofKCIBknX1Tp5h6HxPgxFngV0Jxjt8pyiKQ0Cqfv6kCRTzGrwYczywQbGGDxSBAFZ+sXNRNcWVURLY2fuLOXygwA8BK7b13MA5nmuYqVRYucHa8P8Y+gd1zLtMhm9SsAKs3Nl9/eBxtkvVOL14sgeX13mF3mXPDeEDBfrTsJXbD1w3eHI0fAAYPGEAgDAJ3BI+UIBtgEAw1OTz8udUlce898ETBnr6NSDLCs1N4QMFJoDZ4Js51VNdP2Ns5ZWtBG4LHyggAeJb+7OmKRApgRvDBwpEgGRdPVESuDV8oAAESNfPz1YCN4cP5Hkv4MevHZxfU012Ic3FHLOmjX6MvsN6zPTBEwY8HqDx0sQ36Mrn8L+4uXsehfFXO+swwyhnEa021TJEoQ+1f+/qC88fzFsBVmzrueGjk8aOOdMVz8VT0t9VNZEEHgrUXpR43XwOHwA8zCjjFI22VuIcnKX5TJxOin6ZlwKs3tG99Ogw26lqnPb2awAAuxJQStDS6MXEcT6fn+/knQD3vHRg0ZGhTwd5OAC7EhAA1RVUhm+BvGoEBoKhppm19NnqShKTtCnB4JBhqZxLpynjdhlXoZE3ApitfUJQ21zvw5SauBsywJ4E8cjwE5MXAsR39QgBREogw0/OuAuQrJ+fSoKB4zq4xVEeGX5qxrURmG6Qx5Sgs0/F0KnREKsrCFoaSyyd9Cvk8A2Ff+xhJObHIVU+Mpmk2Gk1QkvP6vSimHIYtOjXBBiMeT1e1wOs2t5z46QJ9OmJ1bFvOBGcA519KlQNaGl078UcXV1djHNu64R3c3NzyuXHpQYw78D53+OgiW6+FI9ZEzDG4XFp+E6R8zZA9O1XDQMIHlRx+pP0YRECGb4D5FSAQDDUdOoT9kL07VftSJAOGb59cnYIuHD71Xqfb19vBOfCn7Y9TAmsHA6S4Ybwq6qqPgZQLbLMnNQA0a39Ei9wlb8E5aWx1Xk2NYEbwgfgIaPAzt++fftSPqvIcQESdfVESuCG8Pv6+qYcOnTonwCq7K47efLk1wYGBi5JNt/RbmC6fn5EA+IPB0DyW7PG44bw+/v7r6WUbgUwPYtijnPOb5s1a9be+BmOCWD1GTuZSuCG8AcGBuoNw3gbY576nREjjLHP1dXVdURPdOQQYOcBS8kOB6lwSfhlhmFshZjwAaCMUrr1gw8+iClPuACBYIgC2AobD1iKlyDV3u+G8AGAMfYbAM2Ci53j8Xjaoic4cggIBEPzAewGUGNnvYgGdIQiaLjU6+rw+/r6pni93gEAPgeKZ5TShhkzZrwPOHQIWNvSsB9AK4BTdtYr8QLXXFHi6vABQFGUFXAmfACgjLF7L7xwaCMZS5CoJeCm8AGAELLK4U3cbY4PODoOkKkE0bgt/IMHD1YBmO3wZibW1tbOAnIwEHRegiXMYJ/YXddt4QOAz+ery8V2NE2rA3I0FLzl589esu2JV0oiYdXyOm4MHwAIITkRwNyO4yeDZi9f/2UAzw0dHfbueqYdN92xCCWlqds3bg0fAJ54N3zzv45Y31ESMbWCYsPn044a1wAO1wBm+Djfoj1xdBi7nmmHmqImcHP444FjAsSHb5JKAhl+7nFEgGThmwwlkECGn1tUVW0EHBAgXfgm0RLI8HOLruvQdX0aIFgAq+GbDB0dxu4X38CIDD+nhMPhC/8L6wXU3bJ+IqF4EjaHMAf6jkDZ/RaaW6/J6v5OxRL+kcNHJw+//5GlZStrL4GveqKt8g3DgGEYUJTR6IUJ0P/CutP1y9YvZwQ7AJTbWffD7kMAkLEExRI+AJw4OVxzuj9kaVlvRaVtASKRSMxroYeAvufXvUo5bgZwzu66H3YfQufut2zf5q+Ywncaxhg0LeaHQuIbgdlK0LXnbZ0QaxWBDN8e8Xs/4FA3sO/5da9yTrZlsKra/+6Hy8u99M50EhRr+GVlpeGSCTWw8ufxlloulzEGVR079uLIUHDdsvW/IARft7maCuCrH2xdtx0AfvpGLz2nscc4H3tUKNbwAaChcc7h45UzhJebKHzAgRrgfPh2n2cTEz4APLzA/0S5l94dXxMUc/hOwRhLWP0DggVIFj4ZvUYwWZtgTPgm5yVYYUogw8+Mc+eSN8eECZAi/E3vb113a5KGYdLwTR5e4H+83EtXKJREZPj2UVUVhpH8jipC2gBpwr8fGG0Y1i9bf3PUOEHa8E0eXuB//KE3ep/esMCvp1u20Ol+9+DsQ529lpad1DgPlVOT/ugHjLGYUb9EZF0DWAnfJKqLeBoWwzdxQ/gAoOu6x4hEYOWPs9RfSTgcRrqrvrMSwE74Jn3Pr3uVM9TZCV9iH13Xxwz6JCJjATIJ36T/hXWnM92uxBojIyOWlsuoDZBN+JLUTJ8+9digZu18WlnNpITTOedg8U/LTIJtAWT4zjJp8qT/VUVs/wo8Bju/9rJ1CJDhFx+WBZDhFyeWBJDhFy9pBZDhFzcpG4Ey/NxTpmBkaoX1phnnfEyjb1KJ9e0lFUCGPz7c1lS673Zi7booTdNSnuixQkLVZPj5j2EYlgd7UjFGABl+/mMYBs6ePWurv5+MmEOADD//EVHtR3OhBpDh5z+apgmp9qNRABl+IaCqqvDwAUCR4ec/4XA46TV92aKAjL1/jww/fxgZGUl6Ra8ICOccs5etfxAEvwJk+OPNwMDAXF3XbwIATdOmaZpm7/GxFqGU/q2pqenRCzeKnLPsZ/eD8JkyfHfxf+pORKaa6AajAAAAAElFTkSuQmCC)
코로나-19를 해결하기 위해 뛰어난 학자들이 한데 모여 연구에 매진했다. 그 결과 매우 효과적으로 바이러스를 치료할 수 있는 백신을 개발해내는데 성공하였다. 이 백시은 한 명의 환자에게 접종하면 바이러스와 유사한 방식으로 해당 사람과 밀접하게 접촉하는 사람들에게 전파되어 그 사람들까지 모두 치료한다. 매우 효과적이고 빠른 속도로 전파되지만, 제작 비용이 너무 많이 든다는 단점으로 인해 현재 프로토 타입으로 제작된 단 하나의 백신만 사용할 수 있는 상황이다.
하나의 백신을 이용하여 가장 많은 사람들을 치료하고자 할 때, 어떤 사람에게 백신을 접종해야 하는지 구해보자.
입력
첫 번째 줄에는 환자들의 수
, 환자 사이 관계의 수
이 공백으로 구분되어 주어진다. ![](https://edu.goorm.io/texconverter?eq=(2%20%5Cleq%20N%2C%20M%20%5Cleq%20200%2C000))
두 번째 줄부터 환자들의 관계가
의 형태로 한 줄에 하나씩 주어진다. 환자들의 관계가
형태로 주어지는 것은 두 환자가 서로 밀접하게 접촉할 수 있음을 뜻한다.
가 한 번 주어진 경우
또는
가 다시 주어지지 않는다.
출력
백신을 가장 많이 퍼뜨리기 위해 접종해야 하는 환자의 번호와 해당 환자에게 백신을 접종했을 때 치료할 수 있는 환자의 수를 공백으로 구분하여 출력한다.
만약 답이 여러 개 존재한다면 접종해야 하는 환자의 번호가 가장 앞 번호인 환자를 출력한다.