Problem:
 Score : 500 points    Problem Statement You are given a connected undirected simple graph, which has N vertices and M edges.
The vertices are numbered 1 through N , and the edges are numbered 1 through M .
Edge i connects vertices A_i and B_i .
Your task is to find a path that satisfies the following conditions:   The path traverses two or more vertices.  The path does not traverse the same vertex more than once.  A vertex directly connected to at least one of the endpoints of the path, is always contained in the path.   It can be proved that such a path always exists.
Also, if there are more than one solution, any of them will be accepted.      Constraints  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq A_i < B_i \leq N  The given graph is connected and simple (that is, for every pair of vertices, there is at most one edge that directly connects them).         Input Input is given from Standard Input in the following format:  N  M  A_1  B_1  A_2  B_2  :  A_M  B_M       Output Find one path that satisfies the conditions, and print it in the following format.
In the first line, print the count of the vertices contained in the path.
In the second line, print a space-separated list of the indices of the vertices, in order of appearance in the path.        Sample Input 1 5 6
1 3
1 4
2 3
1 5
3 5
2 4      Sample Output 1 4
2 3 1 4  There are two vertices directly connected to vertex 2 : vertices 3 and 4 .
There are also two vertices directly connected to vertex 4 : vertices 1 and 2 .
Hence, the path 2 → 3 → 1 → 4 satisfies the conditions.       Sample Input 2 7 8
1 2
2 3
3 4
4 5
5 6
6 7
3 5
2 6      Sample Output 2 7
1 2 3 4 5 6 7

Solution (Python):


import sys
import os


def print_matrix(M):
    print('matrix')
    for i, row in enumerate(M):
        print(i, end=': ')
        print(row)

N, E = list(map(int, input().split()))




M = [[] for j in range(N)]




for _ in range(E):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    
    M[a].append(b)
    
    M[b].append(a)



visited = [False] * N

def get_path(start_index):
    answer = []
    
    answer.append(start_index)
    visited[start_index] = True
    current_index = start_index

    
    while True:
        candidates = M[current_index]
        
        

        next_index = None
        
        for candidate_i in candidates:
            if not visited[candidate_i]:
                
                next_index = candidate_i
                visited[candidate_i] = True
                break
        if next_index is not None:
            answer.append(next_index)
            visited[next_index] = True
            current_index = next_index
        else:
            
            break
    return answer

def check_condition(path):
    left_index = path[0]
    destinations = M[left_index]
    for dest in destinations:
        if not visited[dest]:
            return False, dest

    right_index = path[-1]
    destinations = M[right_index]
    for dest in destinations:
        if not visited[dest]:
            return False, dest
    return True, None


full_path = []
next_index = 0
while True:
    path = get_path(next_index)

    if full_path:
        path.reverse()
        full_path = path + full_path
    else:
        full_path = path

    check_result = check_condition(full_path)
    if check_result[0]:
        
        break
    else:
        
        next_index = check_result[1]



print(len(full_path))
answer2 = []
for v in full_path:
    
    answer2.append(str(v+1))
print(' '.join(answer2))

Solution (Python):

import numpy as np
from collections import deque

N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []
    
visited = [0]*(N+1)
for m in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    if m == 0:
        pt = [A, B]
        visited[A] = 1
        visited[B] = 1


s = pt[0]
add_left = list()

while True:
    left_ext = [l for l in G[s] if visited[l] == 0]
    if len(left_ext) != 0:
        s = left_ext[0]
        visited[s] = 1
        add_left.append(s)
    else:
        break


s = pt[1]
add_right = list()

while True:
    right_ext = [l for l in G[s] if visited[l] == 0]
    if len(right_ext) != 0:
        s = right_ext[0]
        visited[s] = 1
        add_right.append(s)
    else:
        break
pt = list(reversed(add_left)) + pt + add_right
print(len(pt))
print(" ".join([str(a) for a in pt]))

Solution (Python):
from collections import defaultdict, deque
n, m = map(int, raw_input().split())

edge = defaultdict(list)
for _ in xrange(m):
    a, b = map(int, raw_input().split())
    
    
    edge[a].append((a,b))
    edge[b].append((a,b))

i = 1
while not edge[i]:
    i += 1

q = deque()

have_been_to = [False] * (n+1)
have_been_to[i] = True

num_of_edge = [0] * (n+1)
c = 1
path = deque([i])

for d in xrange(2):
    frm = i
    q.extend(edge[i])
    while q:
        (a, b) = q.popleft()
        
        if frm == b and not have_been_to[a] and num_of_edge[a] < 2 and num_of_edge[frm] < 2: 
            q.extendleft(edge[a])
            have_been_to[a] = True
            num_of_edge[a] += 1
            num_of_edge[frm] += 1
            
            if d == 1:
                path.append(a)
            else:
                path.appendleft(a)
            frm = a
            c += 1
        elif frm == a and not have_been_to[b] and num_of_edge[b] < 2 and num_of_edge[frm] < 2: 
            q.extendleft(edge[b])
            have_been_to[b] = True
            num_of_edge[b] += 1
            num_of_edge[frm] += 1
            
            if d == 1:
                path.append(b)
            else:
                path.appendleft(b)
            frm = b
            c += 1
print c
print " ".join(map(str,path))

Solution (Python):
N, M = list(map(int, input().split(" ")))

e = [[] for i in range(N)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    a-=1
    b-=1
    e[a].append(b)
    e[b].append(a)

ch = [False for i in range(N)]
right = []
ch[0]=True

now = 0
while 1:
    for i in e[now]:
        if ch[i] == False:
            ch[i] = True
            now = i
            right.append(i)
            break
    else:
        break

left = []

now = 0
while 1:
    for i in e[now]:
        if ch[i] == False:
            ch[i] = True
            now = i
            left.append(i)
            break
    else:
        break

res = left[::-1] + [0] + right
for i in range(len(res)):
    res[i] = str(res[i]+1)
print(len(res))
print(" ".join(res))

Solution (Python):
import heapq
def dijkstra_path(V, source, target):

    visited = [False] * V
    prev = [-1 for i in range(V)]


    dist = [float('inf')] * V
    dist[source] = 0

    h = [(0, source)]
    while h:
        c, v = heapq.heappop(h)
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(graph[v])):
            t = graph[v][i]
            nc = c + 1
            if dist[t] > nc:
                dist[t] = nc
                heapq.heappush(h, (nc, t))
                prev[t] = v
    path = [target]
    while path[-1] != source and path[-1] != -1:
        path.append(prev[path[-1]])
    return path[::-1]

def all_contains(s, a):
    return all([x in s for x in a])

n,m=map(int, input().split())
graph = [[] for i in range(n)]
cnt = [0 for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cnt[a-1] += 1
    cnt[b-1] += 1
start = 0
end = 1
for i in range(n):
    if cnt[i]<=cnt[start]:
        end = start
        start = i


def main():
    v = start
    path = [start]
    moved = [0 for i in range(n)]
    pre = [float('inf') for i in range(n)]
    while True:
        if path[-1] != v:
            path.append(v)
        
        if all_contains(path, graph[v]) and all_contains(path, graph[start]):
            return path

        while moved[v] < len(graph[v]):
            nv = graph[v][moved[v]]
            if nv not in path:
                pre[nv] = v
                moved[v] += 1
                v = nv
                break
            else:
                moved[v] += 1
        else:
            path.pop()
            moved[v] = 0
            v = pre[v]



def allow_path(path):
    for i in range(len(path)-1):
       if not path[i+1] in graph[path[i]]:
           print(i+1, path[i+1], 'not in ', graph[path[i]])
           return False
    return True

if __name__ == '__main__':
    if cnt[end] == 1:
        res = dijkstra_path(n, start, end)
    else:
        res = main()
    
    print(len(res))
    print(' '.join([str(x+1) for x in res]))

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10**7)

def solve():
    def dfs1(u, path, visited):
        for w in Adj[u]:
            if not visited[w]:
                path.append(w)
                visited[w] = True
                dfs1(w, path, visited)
                return

    def dfs2(u, path, visited):
        for w in Adj[u]:
            if not visited[w]:
                path.appendleft(w)
                visited[w] = True
                dfs2(w, path, visited)
                return

    N, M = map(int, sys.stdin.readline().split())
    Adj = [[] for i in range(N)]

    for i in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1
        Adj[a].append(b)
        Adj[b].append(a)

    if any(len(v) == 1 for v in Adj):
        for i, v in enumerate(Adj):
            if len(v) == 1:
                s = i
                break

        path = [s]
        visited = [False] * N
        visited[s] = True

        dfs1(s, path, visited)

        path = [i + 1 for i in path]

        print(len(path))
        print(*path)
    else:
        s = 0
        path = deque([0])

        visited = [False] * N
        visited[s] = True

        dfs1(s, path, visited)
        dfs2(s, path, visited)

        path = [i + 1 for i in path]

        print(len(path))
        print(*path)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Solution (Python):

temp=input().split()
N=int(temp[0])
M=int(temp[1])
AB=[[int(j)-1 for j in input().split()] for i in range(M)]

chain=[[] for i in range(N)]
used=[False for i in range(N)]
ans=[]


for i in range(M):
	chain[AB[i][0]].append(AB[i][1])
	chain[AB[i][1]].append(AB[i][0])





start=0
while len(chain[start])==0:
	start+=1
ans.append(start)
used[start]=True
next=start



while True:
	
	for point in chain[next]:
		if used[point]==False:
			break
	else:
		break
	
	used[point]=True
	next=point
	ans.append(point)

while True:
	for point in chain[start]:
		if used[point]==False:
			break
	else:
		break
	used[point]=True
	start=point
	ans.insert(0,start)
print(len(ans))
ANS=""
for i in ans:
	ANS+=str(i+1)+" "
print(ANS[:-1])

Solution (Python):



from random import *
from functools import reduce,partial

def readln():
    return list(map(int,input().split(' ')))

def identity(x):
    """Return the input itself."""
    return x

def constant(c):
    """Return an function which always
    returns the input constant c."""
    def const_function(const,*args):
        return const
    return partial(const_function,c)

def inc(c = 1):
    """Return a function which reads an input x and returns x + c as output.
    By default, c equals 1."""
    return lambda x: x + c

def add(*args):
    """Return the sum of the input."""
    def add2(x,y): return x + y
    return reduce(add2,args)

def mapv(f,*lst):
    """Return a vector of the result of map."""
    return list(map(f,*lst))

def vector(*args):
    """Return a vector of input parameters."""
    return args

def sequence(n,f = constant(0)):
    """Return a vector of length n, and initialize the i'th
    item with f(i).By default the vector will initialized with 0."""
    return [f(i) for i in range(0,n)]

def matrix(n,m,f = constant(0)):
    """Return a 2-dim vector which contains n vectors with length m.
    The j's item of vector i will be initialized by f(i,j).By default,
    the vector will be initialized with 0."""
    return [[f(i,j) for j in range(0,m)] for i in range(0,n)]

def flat(v):
    """Return a flat vector which contains the elements of v in their
    origin order.If the input is not a vector, return a vector which
    only contains the input."""
    if not isinstance(v,list): return [v]
    if not v: return []
    return reduce(add,mapv(flat,v))

def partition(v,f = identity):
    """Partition vector v by f(v[i]).
    e.g. partition([1,2,3,1,2,3],identity()) == {1:[1,1,1], 2:[2,2], 3:[3]}
    By default, the vector will be partitioned by identity function."""
    result = {}
    for item in v:
        key = f(item)
        s = result.get(key)
        if s:
            s.append(item)
        else:
            result.update({key:[item]})
    return result

def getValue(key):
    """Return a function which returns the value of key in a hash-map.
    If the key do not exist, it will throw an error."""
    return lambda x: x[key]

def mapValue(f,m):
    """Replace each value in hash-map m with f(value).
    Return the new hash-map."""
    res = {}
    for key in m:
        res.update({key: f(m[key])})
    return res

n,m = readln()
e = [set() for i in range(n + 1)]
for i in range(m):
    s,t = readln()
    e[s].add(t)
    e[t].add(s)
v = sequence(n + 1,constant(True))
q = sequence(n + 1)
q[0] = 1
p = q[:]
v[1] = False
i = 0
while q[i] > 0:
    s = q[i]
    for t in e[s]:
        if v[t]:
            v[t] = False
            q[i + 1] = t
            break
    i = i + 1
j = 0
while p[j] > 0:
    s = p[j]
    for t in e[s]:
        if v[t]:
            v[t] = False
            p[j + 1] = t
            break
    j = j + 1

print(i + j - 1)
for k in range(1,i):
    print(q[i - k],end = ' ')
for k in range(0,j):
    print(p[k],end = ' ')

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    la = [None] * (n + 1)
    xt = [None] * len(dat)
    j = 0
    for i in xrange(m):
        x, y = dat[j:j+2]
        xt[j] = la[y]
        xt[j+1] = la[x]
        la[y] = j
        la[x] = j + 1
        j += 2
    done = [None] * (n + 1)
    x = 1
    po = []
    while 1:
        po.append(x)
        done[x] = 1
        y = la[x]
        while y is not None:
            z = dat[y]
            if done[z] is None:
                x = z
                break
            y = xt[y]
        else:
            break
    x = 1
    pa = []
    while 1:
        pa.append(x)
        done[x] = 1
        y = la[x]
        while y is not None:
            z = dat[y]
            if done[z] is None:
                x = z
                break
            y = xt[y]
        else:
            break
    po = po[::-1] + pa[1:]
    print len(po)
    print ' '.join(map(str, po))
main()

Solution (Python):
n, m = [int(x) for x in raw_input().split()]

t = [[] for i in xrange(n)]

for i in xrange(m):
    a, b = [int(x) - 1 for x in raw_input().split()]
    t[a].append(b)
    t[b].append(a)

pre = [a]
pos = [b]
visited = {a, b}

while 1:
    for ne in t[pre[-1]]:
        if ne not in visited:
            visited.add(ne)
            pre.append(ne)
            break
    else:
        break


while 1:
    for ne in t[pos[-1]]:
        if ne not in visited:
            visited.add(ne)
            pos.append(ne)
            break
    else:
        break

print(len(pre) + len(pos))
print(" ".join(str(x + 1) for x in reversed(pre)) + " " + " ".join(str(x + 1) for x in pos))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

N,M = map(int, raw_input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    A,B = map(int, raw_input().split())
    E[A-1] += [B-1]
    E[B-1] += [A-1]
U = [False]*N
ans = []
def BT(p, ans):
    global U
    for e in E[p]:
        if not U[e]:
            U[e] = True
            ans += [e]
            BT(e, ans)
            break
U[0] = True
for i in range(2):
    ans += [[]]
    BT(0, ans[i])
print len(ans[0])+1+len(ans[1])
print " ".join([str(x+1) for x in ans[0]][::-1]+["1"]+[str(x+1) for x in ans[1]])