Maximum Magic Walk

Given is an undirected weighted graph with n vertices and m edges. There may be self loops and/or multiple edges in the graph. A u-v walk is defined as a sequence of vertices starting at u and ending at v, where consecutive vertices in the sequence are adjacent vertices in the graph i.e. consecutive vertices are connected by some edge. An arbitary walk of length k+1 is, V1,E1,V2,E2,V3,...,Vk,Ek,