在 Moldova 王国有 个用双向道路连接着的城市，编号为 到 。为了节约开支，政府建了 条双向道路连接这些城市，使得任意两个城市之间可以互相到达。因为一条法令，这 个城市各自有着非负数的美化指数比如第 个城市的美化指数等于 。不同的城市可能有着相同的美化指数。Gigel 来到了 Moldova 王国，且现在在第 个城市。他早就迫不及待地想要参观这些美丽的城市，但是因为时间有限，他犹豫着无法决定去哪些城市。他将在 Moldova 王国停留 天，每天他可以去参观一些城市。在第 天，他将会从前一天停留的城市 开始（如果 ，则 )，前往另一个城市 ，而城市 是最大化 的城市。其中 是从城市 到城市 所需经过的最少的道路条数。如果有多个城市同时取得最大值，则选定编号最小的城市。然后第 天他会在城市 停留一整天。第二天他又会重复这一进程。Gigel 想要知道第 天他会在哪个城市停留一整天，于是他来请求你的帮助。
第一行包含两个数字，城市的数量 ，和 Gigel 参观城市的天数 。
第二行包含 个用空格隔开的 个数字 ， 表示第 个城市的美化指数。
接下来的 行，每行包括两个数字 ，表示城市 和城市 之间有一条双向道路直接相连。
输出第 天 Gigel 停留了一整天的城市编号。
5 4 1 1 3 2 4 1 2 1 3 2 4 2 5
5
第一天，Gigel 将会离开城市 前往城市 ；
第二天，他将会离开城市 前往城市 ；
第三天，他将会离开城市 前往城市 ；
第四天，他将会离开城市 前往城市 ；
对于 的数据，，保证城市间是联通的。
