human
She does her utmost to flawlessly carry out a person's last rites and preserve the world's balance of yin and yang.

Hu Tao, being the little prankster she is, has tried to scare you with this graph problem! You are given a connected undirected graph of n nodes with m edges. You also have q queries. Each query consists of two nodes a and b.

Initially, all edges in the graph have a weight of 0. For each query, you must choose a simple path starting from a and ending at b. Then you add 1 to every edge along this path. Determine if it's possible, after processing all q queries, for all edges in this graph to have an even weight. If so, output the choice of paths for each query. 

If it is not possible, determine the smallest number of extra queries you could add to make it possible. It can be shown that this number will not exceed 10^{18} under the given constraints.

A simple path is defined as any path that does not visit a node more than once.

An edge is said to have an even weight if its value is divisible by 2.

Input

The first line contains two integers n and m (2 ≤ n ≤ 3 ⋅ 10^5, n-1 ≤ m ≤ min{\left((n(n-1))/(2), 3 ⋅ 10^5\right)}).

Each of the next m lines contains two integers x and y (1 ≤ x, y ≤ n, x≠ y) indicating an undirected edge between node x and y. The input will not contain self-loops or duplicate edges, and the provided graph will be connected.

The next line contains a single integer q (1 ≤ q ≤ 3 ⋅ 10^5).

Each of the next q lines contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b), the description of each query.

It is guaranteed that nq ≤ 3 ⋅ 10^5.

Output

If it is possible to force all edge weights to be even, print "YES" on the first line, followed by 2q lines indicating the choice of path for each query in the same order the queries are given. For each query, the first line should contain a single integer x: the number of nodes in the chosen path. The next line should then contain x spaced separated integers p_i indicating the path you take (p_1 = a, p_x = b and all numbers should...
Solve the task in PYTHON3.
 ... What is a Python program to determine if it's possible, after processing all q queries, for all edges in this graph to have an even weight?
assistant
#Here is Python program to determine if it's possible, after processing all q queries, for all edges in this graph to have an even weight.

import os,sys
from io import BytesIO,IOBase

def main():
    n,m = map(int,input().split())
    path = [[] for _ in range(n)]
    for _ in range(m):
        u,v = map(lambda xx:int(xx)-1,input().split())
        path[u].append(v)
        path[v].append(u)
    su = [0]*n
    que = [tuple(map(lambda xx:int(xx)-1,input().split())) for _ in range(int(input()))]
    for a,b in que:
        su[a] ^= 1
        su[b] ^= 1
    z = su.count(1)
    if not z:
        print('YES')
        height = [0]*n
        parent = [-1]*n
        st,poi,visi = [0],[0]*n,[1]+[0]*(n-1)
        he = 0
        while len(st):
            x,y = st[-1],path[st[-1]]
            while poi[x] != len(y) and visi[y[poi[x]]]:
                poi[x] += 1
            if poi[x] == len(y):
                st.pop()
                he -= 1
            else:
                z = y[poi[x]]
                he += 1
                height[z] = he
                parent[z] = st[-1]
                st.append(z)
                visi[z] = 1
        for a,b in que:
            ans,ans1 = [a],[b]
            while height[a] > height[b]:
                a = parent[a]
                ans.append(a)
            while height[b] > height[a]:
                b = parent[b]
                ans1.append(b)
            while a != b:
                a,b = parent[a],parent[b]
                ans.append(a)
                ans1.append(b)
            ans1.pop()
            aa = ans+ans1[::-1]
            print(len(aa))
            print(*map(lambda xx:xx+1,aa))
    else:
        print('NO')
        print(z//2)

# Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self,file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd,max(os.fstat(self._fd).st_size,BUFSIZE))
            if not b:
                break
            ptr =...